Re: [algogeeks] Find the duplicate
point to note abt anand's code
reason why it does not work
a] when u r doing xor from index 1 to index n( take two cases that n/2
is od or even)
resulting xor will be an xor impression of non repeating number +
either 0 or 1 time the repeating number
now you start xoring again from index zero, so in worst case, xor will
have value equal to a[0], it may or may not be repeating element(all
other numbers will result in zero as they are xored even number of
times)
the expression if(xor == arr[i]) is luck by chance thing it may be
right, it may not be...
main(){
int arr[]={3,9,3,5,3,6,1,4,3,3};
int len,i,set_bit_no;
int x,y,temp;
x=y=0;
len = sizeof(arr)/sizeof(arr[0]);
int xor = arr[0];
for(i=1;ilen;i++)
{
xor ^= arr[i];
}
printf(xor:%d\n,xor);
for(i=0;ilen;i++)
{
xor ^= arr[i];
if(xor == arr[i])
{
printf(NUM REPEATED:%d\n,arr[i]);
break;
}
}}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sat, Aug 7, 2010 at 3:25 AM, Manjunath Manohar
manjunath.n...@gmail.comwrote:
i kinda understood ...u are doing xor on the array twice..but it dint seem
to work for the array..{2,1,3,2}
please elaborate ur code...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
how about using hashing??? at the first collision we will know the repeated element worst case time here will be ( n/2 +1 ) On Fri, Aug 6, 2010 at 12:04 AM, Anand anandut2...@gmail.com wrote: http://codepad.org/8eDVyeBT Using XOR logic we can find Duplicates in O(n) On Thu, Aug 5, 2010 at 11:25 AM, ravindra patel ravindra.it...@gmail.comwrote: Your test case is wrong. With this pattern you can have at max n/3 occurrences of 1. The questions says that repeated element has n/2 occurrences On Thu, Aug 5, 2010 at 8:37 PM, Manjunath Manohar manjunath.n...@gmail.com wrote: consider the test case of... 1 2 3 1... 1 repeated n/2 times and 2,3 are distinct n/2 elements for this the algo will not work -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
Using median, you can do it! Thanks, Sathaiah On Thu, Aug 5, 2010 at 7:06 PM, AlgoBoy manjunath.n...@gmail.com wrote: an array in which n/2 elements are unique...and the remaning n/2 have the same elements but reapeated n/2 times. can anyone suggest a linear solution with constant space/... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
no the array is unsorted.. On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal bansal...@gmail.com wrote: If I understand the question correctly... there is an array of size n which has n/2 distinct elements and one element is repeated n/2 times. For e.g.: n = 4: 1 2 3 3 n = 61 2 3 4 4 4 n = 81 2 3 4 5 5 5 5 So now this problem can be reduced to finding the first duplicate element in the array because remaining other elements will be unique. I think this can be done in linear time. On Thu, Aug 5, 2010 at 7:06 PM, AlgoBoy manjunath.n...@gmail.com wrote: an array in which n/2 elements are unique...and the remaning n/2 have the same elements but reapeated n/2 times. can anyone suggest a linear solution with constant space/... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
Hey Anand, Can you(or anyone who understood it) elaborate on that XOR logic idea of yours? Thanks, Seckin On Fri, Aug 6, 2010 at 7:14 AM, Manjunath Manohar manjunath.n...@gmail.comwrote: no the array is unsorted.. On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal bansal...@gmail.com wrote: If I understand the question correctly... there is an array of size n which has n/2 distinct elements and one element is repeated n/2 times. For e.g.: n = 4: 1 2 3 3 n = 61 2 3 4 4 4 n = 81 2 3 4 5 5 5 5 So now this problem can be reduced to finding the first duplicate element in the array because remaining other elements will be unique. I think this can be done in linear time. On Thu, Aug 5, 2010 at 7:06 PM, AlgoBoy manjunath.n...@gmail.com wrote: an array in which n/2 elements are unique...and the remaning n/2 have the same elements but reapeated n/2 times. can anyone suggest a linear solution with constant space/... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
hi anand.. can u write up a pseudocode of ur algorithm using XOR logic -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
i kinda understood ...u are doing xor on the array twice..but it dint seem
to work for the array..{2,1,3,2}
please elaborate ur code...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
yeah it does not work. maybe it is only the implementation being wrong, I
want to hear the idea.
On Fri, Aug 6, 2010 at 2:55 PM, Manjunath Manohar
manjunath.n...@gmail.comwrote:
i kinda understood ...u are doing xor on the array twice..but it dint seem
to work for the array..{2,1,3,2}
please elaborate ur code...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
The thread is waiting for u anand :)..reply soon -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
@Algoboy , its pretty difficult to find the duplicate in constant space unless u mention the range of numbers. Do the numbers lie between [1,n] ??? Unless some other information is given i don't think it is possible to come out with a proper solution. -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
travse array and check that if(a[i]==a[i+1]||a[i]==a[i+2]); if more then n/2 no are there then that condition will satisfy ...adjust with boundary condition On Thu, Aug 5, 2010 at 6:36 AM, AlgoBoy manjunath.n...@gmail.com wrote: an array in which n/2 elements are unique...and the remaning n/2 have the same elements but reapeated n/2 times. can anyone suggest a linear solution with constant space/... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
consider the test case of... 1 2 3 1... 1 repeated n/2 times and 2,3 are distinct n/2 elements for this the algo will not work -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
If I understand the question correctly... there is an array of size n which has n/2 distinct elements and one element is repeated n/2 times. For e.g.: n = 4: 1 2 3 3 n = 61 2 3 4 4 4 n = 81 2 3 4 5 5 5 5 So now this problem can be reduced to finding the first duplicate element in the array because remaining other elements will be unique. I think this can be done in linear time. On Thu, Aug 5, 2010 at 7:06 PM, AlgoBoy manjunath.n...@gmail.com wrote: an array in which n/2 elements are unique...and the remaning n/2 have the same elements but reapeated n/2 times. can anyone suggest a linear solution with constant space/... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
In constant space??? How? will you please elaborate? On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal bansal...@gmail.com wrote: If I understand the question correctly... there is an array of size n which has n/2 distinct elements and one element is repeated n/2 times. For e.g.: n = 4: 1 2 3 3 n = 61 2 3 4 4 4 n = 81 2 3 4 5 5 5 5 So now this problem can be reduced to finding the first duplicate element in the array because remaining other elements will be unique. I think this can be done in linear time. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
compare pair wise i.e a[0] and a[1]a[2] and a[3].. leave out last 4 elements... repeated element can be found in 3 comparison for these 3 elements... total no of comparison in worst case (n/2+1) Negi On Thu, Aug 5, 2010 at 10:55 PM, Shiv ... shivsinha2...@gmail.com wrote: In constant space??? How? will you please elaborate? On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal bansal...@gmail.com wrote: If I understand the question correctly... there is an array of size n which has n/2 distinct elements and one element is repeated n/2 times. For e.g.: n = 4: 1 2 3 3 n = 61 2 3 4 4 4 n = 81 2 3 4 5 5 5 5 So now this problem can be reduced to finding the first duplicate element in the array because remaining other elements will be unique. I think this can be done in linear time. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
Your test case is wrong. With this pattern you can have at max n/3 occurrences of 1. The questions says that repeated element has n/2 occurrences On Thu, Aug 5, 2010 at 8:37 PM, Manjunath Manohar manjunath.n...@gmail.comwrote: consider the test case of... 1 2 3 1... 1 repeated n/2 times and 2,3 are distinct n/2 elements for this the algo will not work -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
Nice solution. Reduces number of comparisons to half of Ashish's algo. The complexity remains O[n] though. Can it be made more efficient, like O[log n] On Thu, Aug 5, 2010 at 10:59 PM, Pramod Negi negi.1...@gmail.com wrote: compare pair wise i.e a[0] and a[1]a[2] and a[3].. leave out last 4 elements... repeated element can be found in 3 comparison for these 3 elements... total no of comparison in worst case (n/2+1) Negi On Thu, Aug 5, 2010 at 10:55 PM, Shiv ... shivsinha2...@gmail.com wrote: In constant space??? How? will you please elaborate? On Thu, Aug 5, 2010 at 9:29 PM, dinesh bansal bansal...@gmail.comwrote: If I understand the question correctly... there is an array of size n which has n/2 distinct elements and one element is repeated n/2 times. For e.g.: n = 4: 1 2 3 3 n = 61 2 3 4 4 4 n = 81 2 3 4 5 5 5 5 So now this problem can be reduced to finding the first duplicate element in the array because remaining other elements will be unique. I think this can be done in linear time. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the duplicate
http://codepad.org/8eDVyeBT Using XOR logic we can find Duplicates in O(n) On Thu, Aug 5, 2010 at 11:25 AM, ravindra patel ravindra.it...@gmail.comwrote: Your test case is wrong. With this pattern you can have at max n/3 occurrences of 1. The questions says that repeated element has n/2 occurrences On Thu, Aug 5, 2010 at 8:37 PM, Manjunath Manohar manjunath.n...@gmail.com wrote: consider the test case of... 1 2 3 1... 1 repeated n/2 times and 2,3 are distinct n/2 elements for this the algo will not work -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
