Nice idea, but unfortunately doesn't work. The XOR only contains parity information. So just pick two values in the range and a low order bit where they're different. Then swap the bits.
2 xor 3 xor 4 xor 5 = 0 Pick 3 and 4 and swap the lsb, which gives 2 and 5. So we have 2 xor 2 xor 5 xor 5 = 0 On Jun 24, 4:12 pm, Piyush Sinha <[email protected]> wrote: > I have a solution that will do the job in O(n) time but will require three > variables....but this solution won't work if the array contains -ve numbers. > * > int findrepeat(int a[],int n) > { > int i,xor = 0; > int min = findmin(a,n); > int max = findmax(a,n); > if((max-min+1)!=n) > return 0; > for(i = 0 ;i<n;i++) > xor^=a[i]; > for(i=min;i<=max;i++) > xor^=i; > if(xor) > return 0; > else > return 1; > > }* > > Please let me know if there is any counter example.. > > > > > > On Sat, Jun 25, 2011 at 1:17 AM, ross <[email protected]> wrote: > > One solution would be to : check if max-min = N and > > that all elements are unique in the array. > > However, this may require space complexity.. Looking for a > > better solution. > > > On Jun 25, 12:44 am, ross <[email protected]> wrote: > > > Given an array, A, find if all elements in the sorted version of A are > > > consecutive in less than O(nlogn). > > > eg: A: 5 4 1 2 3 on sorting 1 2 3 4 5 all elements are consecutive -- > > > true > > > A: 1 9 2 22 on sorting 1 2 9 22 all elements are NOT consecutive - > > > false > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > *Piyush Sinha* > *IIIT, Allahabad* > *+91-8792136657* > *+91-7483122727* > *https://www.facebook.com/profile.php?id=100000655377926* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
