Gene is correct :)
Counter example
{1, 2, 2, 5, 5}
See method 3 here http://geeksforgeeks.org/?p=11516On 6/25/11, Gene <[email protected]> wrote: > 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. > > -- 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.
