0

I have seen the solution for this problem in this thread -> How to find a duplicate element in an array of shuffled consecutive integers?

But the problem I am now having is little varied from it. 

int arr[10] = {1,2,3,4,5,6,7,8,4,9};
    int a= 0;
    for(int i=0;i<10;i++) {
     a= a^ arr[i] ^i;
    }
    cout<<a;

Consider the above mentioned code snippet. Things work fine as it is. But when I add a 0 to the above mentioned array like, int arr[11] = {0,1,2,3,4,5,6,7,8,4,9}; I am not getting the proper duplicate element. Can somebody correct me the mistake I am making here?

Community
  • 1
  • 1
Ajai
  • 3,440
  • 5
  • 28
  • 41
  • 1
    Did you forget to change the for loop? `i<11` instead of `i<10`? The two hardest problems in CS: Naming things, cache invalidation, and off-by-one errors. – krousey Nov 05 '11 at 04:08

3 Answers3

3

The trick relies on the values being between 1 and n. If the numbers are in some other range you'll have to offset them.

static const int n = 11;
int arr[n] = {0,1,2,3,4,5,6,7,8,4,9};
int offset = 1;
int a= 0;
for(int i=0;i<n;i++) {
 a= a^ (arr[i]+offset) ^i;
}
cout<< (a-offset);
Vaughn Cato
  • 63,448
  • 5
  • 82
  • 132
  • I am sorry I just verified this with several other inputs and I think the solution needs to be changed a little bit. This code would work fine if the elements are sorted. What if they are not? It didn't work for the below input, int arr[20] = {0,1,10,3,2,4,5,7,6,8,11,9,15,12,13,4,16,18,17,14}; int offset = 1; int a= 0; for(int i=0;i<20;i++) { a= a^ (arr[i]+offset) ^i; } cout<< (a-offset); – Ajai Nov 05 '11 at 04:28
  • The size of your array is 20, but you have i<11. – Vaughn Cato Nov 05 '11 at 04:29
  • I am terribly sorry for such a mistake. Yes your solution works fine. – Ajai Nov 05 '11 at 04:32
1

I'm guessing it could have to do with the fact that the i value would then be the same as arr[i]

thats like doing:

00000001 ^ 00000001

which equals 00000000

and I may be thinking incorrectly but wouldn't that screw up the process?

DanZimm
  • 2,528
  • 2
  • 19
  • 27
  • Yes I noticed it and I even manually wrote down the output at each iteration and the 0 in the array is the only thing thats making this problem look weird. I am not sure what value to use for a so that the method does not destroys the actual array. – Ajai Nov 05 '11 at 04:09
0

I think i see what happened. you probably changed the loop to be

for(int i=0; i<11; i++)
  ...

since you added an extra element to the loop. the problem is that it's not XORing with 10, which is not a number in your array. So, the algorithm stops working.

int arr[11] = {0,1,2,3,4,5,6,7,8,4,9};
int a= 0;
for(int i=0;i<10;i++) {
  a= a^ arr[i] ^i;
}
a = a^arr[10];

cout<<a;

now, its XORing nums from 0 to 9 twice (which equals zero) and 4 an additional time, so the result should be 4.

aleph_null
  • 5,766
  • 2
  • 24
  • 39