duplicate

Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it? [Read More]

#include <stdio.h\> class BinarySearchTree { private: int data; BinarySearchTree \*left, \*right; public: BinarySearchTree(const int d):data(d), left(NULL), right(NULL){} ~BinarySearchTree() { if(left !\= NULL) { delete left; } if(right !\= NULL) { delete right; } } //remove duplicates void removeDup() { if(left) { left\-\>removeDup(); left\-\>remove(data, this); } if(right) right\-\>removeDup(); } void remove(int value, BinarySearchTree \*parent) { if(value < data && left) { left\-\>remove(value, this); } else if(value \> data && right) { right\-\>remove(value, this); } else remove(parent); } void remove(BinarySearchTree \*parent) //remove this node { if(left \=\= NULL && right \=\= NULL) //leaf { ((parent\-\>left \=\= this) ? [Read More]

Problem For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree. So the tree… 2 / \ 1 3 is changed to… 2 / \ 2 3 / / 1 3 / 1 As with the previous problem, this can be accomplished without changing the root node pointer. [Read More]

**Problem **  Remove duplicates from the sorted array Example [1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5] -> [1, 2, 3, 4, 5] Method 1- using 3 pointers //using 3 pointers fixDuplicatesInSortedArray(Integer$$ a): start = 0 end = 0 destination = 0 while(start < a.length): while(end < a.length && a$end$ == a$start$): end++ end-- //copy the distinct element a$destination$ = a$start$ destination++ start = end + 1 end = start //null out the rest while destination < a. [Read More]

Problem : Remove duplicates from a sorted linked list Example Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. Solutions As the linked list is sorted, we can start from the beginning of the list and compare adjacent nodes. When adjacent nodes are the same, remove the second one. There’s a tricky case where the node after the next node needs to be noted before the deletion. // Remove duplicates from a sorted list void RemoveDuplicates(struct node\* head) { struct node\* current = head; if (current == NULL) return; // do nothing if the list is empty // Compare current node with next node while(current->next! [Read More]

Problem - Given an array of n integers from 1 to n with one integer repeated twice This can be done via normal array traversal or hash table to find duplicates. But since we are given that the integers are from 1 to n, then there are better methods available. Approach 1 - Arithmetic sum approach So, the efficient method to solve it calculate the sum of actual input array, and expected sum of the array. [Read More]