CareerCup

Traverse the array, check your current position + 1 and + 2 for the same value... If at any time while traversing the list you find a duplicate, then you've found the answer. Here are my test cases it works on:

1232
2213
1322
1223

hashtable ?

//'n' is the size of the array 'arr[]'
/*according to the question 'n' has to be even
if 'n' is odd then there is a confusion on what will
be the middle element - unique or non-unique*/

int element(int arr[],int n)
{
    int tmp=0,ele;
    for(int i=0;i<n/2;i++)
    {
        tmp^=arr[i];               //xor operation
    }
    if(tmp==0)
      ele = arr[i-1];
    else
      ele = arr[i]; 
    
    return ele;

}

Time complexity - O(n/2) = O(n)

Start building a binary tree. The moment you hit a previously found node , you have found your non unique element . It will reach an output in less than n iterations.

the constraint that was imposed was, of no additional memory.

NUmber which occured more that n/2 times in the array :

We will sweep down the sequence starting at the pointer position shown above.

As we sweep we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.

When we move the pointer forward over an element e:

* If the counter is 0, we set the current candidate to e and we set the counter to 1.
* If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

When we are done, the current candidate is the majority element, if there is a majority.

I think just need to check next element for each element, but we need to check next two and previous two element resp. in case of first and last element

ex: arr 1 5 2 5 3 5 4 5

a[0]a[1] a[0] a[2]
1 : 5 1 : 2

5 : 2

2 : 5

5 : 3

3 : 5

5 : 4

a[6] a[7] a[5] a[7]
4 : 5 5 : 5 ...... duplicate found

int findRepeated(int * array , int n)
{
for(int i=0,int j = i+1 ; i<n-1 ; i++,j++)
if(array[i]==array[j]) return array[i];

if(array[0]==array[2]) return array[0];
if(array[1]==array[3]) return array[1];
return NOTFOUND;

}

comments ?

three pointer pointing 3 consecutive elements will do the work.

proof: the problem can stated as we have x no of unique element and x no same elements. I want to prove that there will be at least one case where one unique element will be between two same element - thus the two neighboring same and 1 unique kind can be pointed by three pointers and can be compared.

lets assume we've x unique elements and there by (x+1) places to insert x same elements to form the given array. At any point of all possible insertion we can see that either two or more same elements are together (thus can be detected by three pointer comparison). if this is not the case then there will be at most one scenario where two similar element will have 2 unique element between them and rest all cases will have exactly one unique element between them - thus can be detected by three pointer comparison.
---i think this logic is known as Principle of Pigeon Hole to geeks :-)

Algorithm:
i=0 //1st index
j=1 //2nd index
k=2// 3rd index

if elements pointed by i, j and k does not have two common elements
then
i=k+1
j=i+1
k=j+1
else
the common element is the similar element
end if

//Note only i is sufficient, for simplicity j and k are used

Kg,

What if i have array like 6,7,5,3,2,2,2,2. then ur assumption "I want to prove that there will be at least one case where one unique element will be between two same element" does not hold true here?

use hashtabe for searching non unique element.if collision occures then print element.

kg has essence of solution. I convinced by self a little bit differently though.

Suppose you have n/2 unique elements and n/2 same elements in an array of size n (which is even by the way). The same elements exist somewhere in this array by definition, so consider the arrangement where they are maximally distant from each other, meaning each same element is as far away from any other same element as possible.

Clearly we would not want any two same elements to be neighbors.

So we would have an every-other arrangement like "x 1 x 2 x 3 x 4 x 5" or "1 x 2 x 3 x 4 x 5 x" since there are equal numbers of unique and same elements.

Suppose a same element was a distance of 2 from another same element. How would you move from the most distributed arrangement above to the new arrangement with a gap of 2 between same elements? It would have to result in violating the condition that two same elements are neighbors.

This means that for each element, compare it with next neighbor and next next neighbor. If it is equal then that's the "same" element.

int a[10] = {1,3,2,2,4,5,2,2,6,2};

    int res;
    for (int i = 0; i < 10;) {
        res = a[i++];
        if (res == a[i++] || res == a[i++])
            break;
    }

Hash it..

its all bulllshit....
guys this is simple majority finding algorithm...just google out for majority finding algo, and u'll get the solution...

I guess a proof can be given by using a pigeon hole principle.

Algorithm:
i check for a non-unique element in a(1),a(2),a(3). If not i try in a(4) a(5) a(6).. and so on..until end of array
(i give this algorithm because it has an easier proof, not because it is more efficient)
Proof:
If there are no unique element in any such disjoint triplets, then the number of non unique elements cannot be more than ceil(n/3). Thus, there will be one such triplet.

it's like finding the "majority" item...knuth's book has one algo...

v can find this in a single traversal of the array u know..
hav 2 variables a,b and follow the pseudo code below:

i/p: 1 2 3 2 2 4


1)initiate a=0,b=0;
2)read the element and store it in 'a' provided b=0;
3)b is incremented only when next element is equal to a.
4)b is decremented provided if(b>0) and when a!=next element
5)do from step2 till end
finally the value stored in a is the answer

i ll simulate it

a=0
b=0

reading 1
a=1
b=0 (rule 2)

reading 2
a=2
b=0(rule 2)

reading 3
a=3
b=0(rule 2)

reading 2
a=2
b=0(rule 2)

reading 2
a=2
b=1(rule 3) //b alone incremented bcoz a=currelement

reading 4
a=2
b=0(rule 4) //here a is not changed bcoz b was 1 before reading 4//


tell me if any suggestion..

a is incremented when next element is same as in 'a'.. that is a==next element

looks like i have a pretty easu algo.

compare first 3 elements, if any 2 are same, we got the dupe element. return.
Ttranverse the array and compare an element with its adjecent, the one which matches is the dupe.

complexity: O(n)

I didnt get the question.
Can someone provide me an example?

I think we can construct a max-heap for the array. Then traverse the list for atleast one element more than half the array size.
Complexity shld be O(lgn)+O(n)

How about this.

Since 50% are same number and 50% are unique, there is atleast one instance where the non-unique(repeating) numbers are next to each other unless the repeating numbers are alternating between the unique numbers.

So make one pass to see if there are any consecutive repeating number. If none, then check the first four numbers and find the repeating number.

NITW Guy:
Your method works. But "make one pass", how much expensive is that "one pass".
The key is do not make one pass.
Scan first 4 numbers, it costs 6 comparisons.
Move to next 4 numbers, it costs 12 now.
Keep going on n/6 time, if we do not find a duplicate number, go for one more time. This time we are sure to find the duplicate number.
Since each time, if we are not lucky, we get the duplicate number say d, and other 3 unique numbers.
If it goes on n/6 time, we scan through n/2 unique numbers plus d. We will surely get at least 3 d's and perhaps one more unique number(considering n= odd). So, the algorithm has n+4 comparisons.

NITW Guy:
Check first 4 after a pass is not enough if n is odd.
One example:
1, 4, 2, 3, 4, 5, 4, 6
In this case, the first 4 does not duplicated.

correction:
The example should be:
1, 4, 2, 3, 4, 5, 4, 6, 4.

I haven't read the other solutions so my solution might be a subset or super set of other solutions.
Here is the pseudo code ( Assuming n is even, though for odd as similar solution would suffice)
1. Break the array into groups of 2 elements each
2. Compare the two elements ( this will order n as there will be n/2 comparisons)
3. Now there can be 2 cases
1. In one of the group the element is same, Hence that element is non unique.
2. All groups don't have same element. This means that there is one unique and one non unique element. Hence just compare any 2 groups randomly and you will get the non-unique element. This will 3 more comparison hence order of algorithm remains O(n)

Majority element problem: one element appearing more than (or equal) the half size of the array.

not read the solution but
i think simply traverse the array....keep a note of two consecutive elements before the current element..i.e check a[i] with a[i-1] a[i-2]...worst case first n/2 elements are unique and last n/2 are repeated so wud traverse half the array....
i=2;
while(i<n)
{
if(a[i]==a[i-1]||a[i]==a[i-2]) {cout<<a[i]; exit;}
}

worst case can be more than n/2 comparisons anyways wud be O(n) then also...i think saurabh's algo is better...gives sure n/2+3 comparison solution

worst case can be more than n/2 comparisons anyways wud be O(n) then also...i think saurabh's algo is better...gives sure n/2+3 comparison solution