Re: [algogeeks] Re: Find the non-duplicate element in sorted array in O(n) time
{ 1,1,2,2,2,2,3,3,3,4,4,5,5}, here 3 is missing its pair, does this also
comes under this problem?
surender
On Thu, Aug 25, 2011 at 8:12 AM, Dave dave_and_da...@juno.com wrote:
@Shailesh: Sir, your response is unresponsive, because the original
poster specifically asked for a solution that was O(n). Please don't
waste our time giving answers that so obviously do not meet the
problem statement.
Dave
On Aug 24, 6:33 pm, smb shaileshbir...@gmail.com wrote:
XOR all the elements, the answer is the number you want.
On Aug 24, 5:11 pm, Don dondod...@gmail.com wrote:
I assume that elements in pairs means that each value occurs exactly
twice except for the one single.
This algorithm is O(log n) and is nonrecursive. Writing it recursively
would make it a couple of lines shorter, but because it is purely tail
recursion, that is not necessary.
// Given an array a of size elements in which all elements occur in
pairs except for one single item,
// find the single item and return its value.
int findSingle(int *a, int size)
{
while(1)
{
// For an array of size 1, the only element is the single.
if (size == 1) return a[0];
// The logic below won't work for size three, but it is simple to
find the single.
else if (size == 3) return (a[0] == a[1]) ? a[2] : a[0];
else
{
// Pick the midpoint of the array
int midpoint = size/2;
// If we are looking at the second element of a pair, move back
to the first element
if (a[midpoint] == a[midpoint-1]) --midpoint;
// If midpoint is not a pair, that is the single.
else if (a[midpoint] != a[midpoint+1]) return a[midpoint];
// If midpoint is odd, look at left half of the array
if (midpoint % 2) size = midpoint;
else // If midpoint is even, look at the right half of the array
{
a += midpoint;
size -= midpoint;
}
}
}
}
On Aug 24, 4:49 am, atul purohit gonewiththe...@gmail.com wrote:
Hi,
A* sorted *integer array contains elements in pairs. All the pairs
are
complete except one element whose pair is missing. Find that element.
Ex. { 1,1,2,2,2,2,3,3,4,5,5}
result = 5
There is a standard solution which returns an XOR of all the
elements. But
this needs O(n) time complexity. The person who asked me this
question said
that this can be done in O(n). Maybe we can eliminate some
elements.
Anyone knows how to do this?
Cheers,
Atul- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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] Re: Find the non-duplicate element in sorted array in O(n) time
How about this :
We use a divide and conquer approach and since the array is sorted.
We find the middle element and check its value with its immediate left and
right element .. it must match with anyone of them ..
if it doesnt we have found such a element . and otherwise we divide the
array again ..
and then again find the middle element .. to check the same condition ..
This will take O(lg n ) time :)
On Wed, Aug 24, 2011 at 3:45 PM, Venkat venkataharishan...@gmail.comwrote:
we can solve this with the help of binary search.
we know N, which is odd(because of one pair missing)
We divide it array. Let consider your input { 1,1,2,2,2,2,3,3,4,5,5}
int find_culprit(int[] array, int start, int end)
{
if(end==start)
return -1;
int mid=((end-start) / 2) + start;
if array[mid] == array[mid-1]
return find_culprit(mid,end)
if(array[mid] == array [mid +1]
return find_culprit(start, mid);
else
return array[mid];
}
Run through:
Steps1: find_culprit(array,0,8)
mid=4
Step 2 : find_culprit(array,4,8))
mid=6
step 3 : find_culprit(array,6,8))
mid=7
return array[7]=4 (which dont have pair)
Run time O(log n+1) = O(log n)
Please ask if you ve any doubts.
Regards
Venkat.
On Aug 24, 2:49 pm, atul purohit gonewiththe...@gmail.com wrote:
Hi,
A* sorted *integer array contains elements in pairs. All the pairs are
complete except one element whose pair is missing. Find that element.
Ex. { 1,1,2,2,2,2,3,3,4,5,5}
result = 5
There is a standard solution which returns an XOR of all the elements.
But
this needs O(n) time complexity. The person who asked me this question
said
that this can be done in O(n). Maybe we can eliminate some elements.
Anyone knows how to do this?
Cheers,
Atul
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
The more you sweat in the field, the less you bleed in war.
Ankit Minglani
NITK Surathkal
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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] Re: Find the non-duplicate element in sorted array in O(n) time
@Venkat : suppose if the array were : 1 2 2 2 2 2 2 2 2 2 2, would ur
solution work ?
Sanju
:)
On Wed, Aug 24, 2011 at 3:58 AM, Ankit Minglani ankit.mingl...@gmail.comwrote:
How about this :
We use a divide and conquer approach and since the array is sorted.
We find the middle element and check its value with its immediate left and
right element .. it must match with anyone of them ..
if it doesnt we have found such a element . and otherwise we divide the
array again ..
and then again find the middle element .. to check the same condition ..
This will take O(lg n ) time :)
On Wed, Aug 24, 2011 at 3:45 PM, Venkat venkataharishan...@gmail.comwrote:
we can solve this with the help of binary search.
we know N, which is odd(because of one pair missing)
We divide it array. Let consider your input { 1,1,2,2,2,2,3,3,4,5,5}
int find_culprit(int[] array, int start, int end)
{
if(end==start)
return -1;
int mid=((end-start) / 2) + start;
if array[mid] == array[mid-1]
return find_culprit(mid,end)
if(array[mid] == array [mid +1]
return find_culprit(start, mid);
else
return array[mid];
}
Run through:
Steps1: find_culprit(array,0,8)
mid=4
Step 2 : find_culprit(array,4,8))
mid=6
step 3 : find_culprit(array,6,8))
mid=7
return array[7]=4 (which dont have pair)
Run time O(log n+1) = O(log n)
Please ask if you ve any doubts.
Regards
Venkat.
On Aug 24, 2:49 pm, atul purohit gonewiththe...@gmail.com wrote:
Hi,
A* sorted *integer array contains elements in pairs. All the pairs are
complete except one element whose pair is missing. Find that element.
Ex. { 1,1,2,2,2,2,3,3,4,5,5}
result = 5
There is a standard solution which returns an XOR of all the elements.
But
this needs O(n) time complexity. The person who asked me this question
said
that this can be done in O(n). Maybe we can eliminate some elements.
Anyone knows how to do this?
Cheers,
Atul
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
The more you sweat in the field, the less you bleed in war.
Ankit Minglani
NITK Surathkal
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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] Re: Find the non-duplicate element in sorted array in O(n) time
yes this is the only one till now, but i think we can do better also.
Hope a better solution will be posted by someone soon.
Sanju
:)
On Wed, Aug 24, 2011 at 5:22 AM, Venkat venkataharishan...@gmail.comwrote:
@Sanju: For your input both above solution wont work...
Do you ve any soultion for your input??
For your input Xor all numbers - will give you the result:)
but its O(n)
Anyway your input allow everyone to think little wider than Binay
search.
Thanks
Venkat
On Aug 24, 4:05 pm, Sanjay Rajpal srn...@gmail.com wrote:
@Venkat : suppose if the array were : 1 2 2 2 2 2 2 2 2 2 2, would ur
solution work ?
Sanju
:)
On Wed, Aug 24, 2011 at 3:58 AM, Ankit Minglani
ankit.mingl...@gmail.comwrote:
How about this :
We use a divide and conquer approach and since the array is sorted.
We find the middle element and check its value with its immediate left
and
right element .. it must match with anyone of them ..
if it doesnt we have found such a element . and otherwise we divide the
array again ..
and then again find the middle element .. to check the same condition
..
This will take O(lg n ) time :)
On Wed, Aug 24, 2011 at 3:45 PM, Venkat venkataharishan...@gmail.com
wrote:
we can solve this with the help of binary search.
we know N, which is odd(because of one pair missing)
We divide it array. Let consider your input { 1,1,2,2,2,2,3,3,4,5,5}
int find_culprit(int[] array, int start, int end)
{
if(end==start)
return -1;
int mid=((end-start) / 2) + start;
if array[mid] == array[mid-1]
return find_culprit(mid,end)
if(array[mid] == array [mid +1]
return find_culprit(start, mid);
else
return array[mid];
}
Run through:
Steps1: find_culprit(array,0,8)
mid=4
Step 2 : find_culprit(array,4,8))
mid=6
step 3 : find_culprit(array,6,8))
mid=7
return array[7]=4 (which dont have pair)
Run time O(log n+1) = O(log n)
Please ask if you ve any doubts.
Regards
Venkat.
On Aug 24, 2:49 pm, atul purohit gonewiththe...@gmail.com wrote:
Hi,
A* sorted *integer array contains elements in pairs. All the pairs
are
complete except one element whose pair is missing. Find that
element.
Ex. { 1,1,2,2,2,2,3,3,4,5,5}
result = 5
There is a standard solution which returns an XOR of all the
elements.
But
this needs O(n) time complexity. The person who asked me this
question
said
that this can be done in O(n). Maybe we can eliminate some
elements.
Anyone knows how to do this?
Cheers,
Atul
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
The more you sweat in the field, the less you bleed in war.
Ankit Minglani
NITK Surathkal
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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] Re: Find the non-duplicate element in sorted array in O(n) time
Hi
The ques explicitly said the elements are in pairs ...But the one given by
sanjay has more than 2 2's ...that question cant be done using bsearch then
On Wed, Aug 24, 2011 at 6:21 PM, Sanjay Rajpal srn...@gmail.com wrote:
yes this is the only one till now, but i think we can do better also.
Hope a better solution will be posted by someone soon.
Sanju
:)
On Wed, Aug 24, 2011 at 5:22 AM, Venkat venkataharishan...@gmail.comwrote:
@Sanju: For your input both above solution wont work...
Do you ve any soultion for your input??
For your input Xor all numbers - will give you the result:)
but its O(n)
Anyway your input allow everyone to think little wider than Binay
search.
Thanks
Venkat
On Aug 24, 4:05 pm, Sanjay Rajpal srn...@gmail.com wrote:
@Venkat : suppose if the array were : 1 2 2 2 2 2 2 2 2 2 2, would ur
solution work ?
Sanju
:)
On Wed, Aug 24, 2011 at 3:58 AM, Ankit Minglani
ankit.mingl...@gmail.comwrote:
How about this :
We use a divide and conquer approach and since the array is sorted.
We find the middle element and check its value with its immediate left
and
right element .. it must match with anyone of them ..
if it doesnt we have found such a element . and otherwise we divide
the
array again ..
and then again find the middle element .. to check the same condition
..
This will take O(lg n ) time :)
On Wed, Aug 24, 2011 at 3:45 PM, Venkat venkataharishan...@gmail.com
wrote:
we can solve this with the help of binary search.
we know N, which is odd(because of one pair missing)
We divide it array. Let consider your input { 1,1,2,2,2,2,3,3,4,5,5}
int find_culprit(int[] array, int start, int end)
{
if(end==start)
return -1;
int mid=((end-start) / 2) + start;
if array[mid] == array[mid-1]
return find_culprit(mid,end)
if(array[mid] == array [mid +1]
return find_culprit(start, mid);
else
return array[mid];
}
Run through:
Steps1: find_culprit(array,0,8)
mid=4
Step 2 : find_culprit(array,4,8))
mid=6
step 3 : find_culprit(array,6,8))
mid=7
return array[7]=4 (which dont have pair)
Run time O(log n+1) = O(log n)
Please ask if you ve any doubts.
Regards
Venkat.
On Aug 24, 2:49 pm, atul purohit gonewiththe...@gmail.com wrote:
Hi,
A* sorted *integer array contains elements in pairs. All the pairs
are
complete except one element whose pair is missing. Find that
element.
Ex. { 1,1,2,2,2,2,3,3,4,5,5}
result = 5
There is a standard solution which returns an XOR of all the
elements.
But
this needs O(n) time complexity. The person who asked me this
question
said
that this can be done in O(n). Maybe we can eliminate some
elements.
Anyone knows how to do this?
Cheers,
Atul
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
The more you sweat in the field, the less you bleed in war.
Ankit Minglani
NITK Surathkal
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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] Re: Find the non-duplicate element in sorted array in O(n) time
See interviewer said that it can be done in O(n) and also only *ONE* pair
is missing i have two approaches
1st approach
check 1st element say n= arr[0] // i=0
now in the for() loop increment i by 2 // i=2
check if arr[i-1]==n? if no, answer is n else n=arr[i] and repeat the same
with i+=2;
2nd approach O(log(n))
do binany search
if suppose upto ith position all elements are in pairs then if 'i' is even
then arr[i]==arr[i+1] else if 'i' is odd then arr[i]==arr[i-1] mean mismatch
is on right side
if above conditions does not met mean upto ith position there is mismatch
so search left side
if arr[i]!=arr[i+1] and arr[i]!=arr[i-1] hence desire o/p if arr[i] ...
i hope i m clear.
On Wed, Aug 24, 2011 at 10:08 PM, Ankur Garg ankurga...@gmail.com wrote:
Hi
The ques explicitly said the elements are in pairs ...But the one given by
sanjay has more than 2 2's ...that question cant be done using bsearch then
On Wed, Aug 24, 2011 at 6:21 PM, Sanjay Rajpal srn...@gmail.com wrote:
yes this is the only one till now, but i think we can do better also.
Hope a better solution will be posted by someone soon.
Sanju
:)
On Wed, Aug 24, 2011 at 5:22 AM, Venkat venkataharishan...@gmail.comwrote:
@Sanju: For your input both above solution wont work...
Do you ve any soultion for your input??
For your input Xor all numbers - will give you the result:)
but its O(n)
Anyway your input allow everyone to think little wider than Binay
search.
Thanks
Venkat
On Aug 24, 4:05 pm, Sanjay Rajpal srn...@gmail.com wrote:
@Venkat : suppose if the array were : 1 2 2 2 2 2 2 2 2 2 2, would ur
solution work ?
Sanju
:)
On Wed, Aug 24, 2011 at 3:58 AM, Ankit Minglani
ankit.mingl...@gmail.comwrote:
How about this :
We use a divide and conquer approach and since the array is sorted.
We find the middle element and check its value with its immediate
left and
right element .. it must match with anyone of them ..
if it doesnt we have found such a element . and otherwise we divide
the
array again ..
and then again find the middle element .. to check the same condition
..
This will take O(lg n ) time :)
On Wed, Aug 24, 2011 at 3:45 PM, Venkat
venkataharishan...@gmail.comwrote:
we can solve this with the help of binary search.
we know N, which is odd(because of one pair missing)
We divide it array. Let consider your input { 1,1,2,2,2,2,3,3,4,5,5}
int find_culprit(int[] array, int start, int end)
{
if(end==start)
return -1;
int mid=((end-start) / 2) + start;
if array[mid] == array[mid-1]
return find_culprit(mid,end)
if(array[mid] == array [mid +1]
return find_culprit(start, mid);
else
return array[mid];
}
Run through:
Steps1: find_culprit(array,0,8)
mid=4
Step 2 : find_culprit(array,4,8))
mid=6
step 3 : find_culprit(array,6,8))
mid=7
return array[7]=4 (which dont have pair)
Run time O(log n+1) = O(log n)
Please ask if you ve any doubts.
Regards
Venkat.
On Aug 24, 2:49 pm, atul purohit gonewiththe...@gmail.com wrote:
Hi,
A* sorted *integer array contains elements in pairs. All the pairs
are
complete except one element whose pair is missing. Find that
element.
Ex. { 1,1,2,2,2,2,3,3,4,5,5}
result = 5
There is a standard solution which returns an XOR of all the
elements.
But
this needs O(n) time complexity. The person who asked me this
question
said
that this can be done in O(n). Maybe we can eliminate some
elements.
Anyone knows how to do this?
Cheers,
Atul
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
The more you sweat in the field, the less you bleed in war.
Ankit Minglani
NITK Surathkal
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email
Re: [algogeeks] Re: Find the non-duplicate element in sorted array in O(n) time
mine approach is log(n)
check it out first
On Thu, Aug 25, 2011 at 1:21 AM, Don dondod...@gmail.com wrote:
I'm going to assume that elements in pairs means exactly two of each
element except for the one which is missing it's pair.
The recursive solution is simple, but it only uses tail recursion, so
it is worthwhile to do it iteratively.
int findSingle(int *a, int size)
{
int result;
while(1)
{
printf(a[0] = %d size=%d\n, a[0], size);
if (size == 1)
{
result = a[0];
break;
}
else if (size == 3)
{
result = (a[0] == a[1]) ? a[2] : a[0];
break;
}
else
{
int midpoint = size/2;
if (a[midpoint] == a[midpoint-1]) --midpoint;
if (a[midpoint] != a[midpoint+1])
{
result = a[midpoint];
break;
}
else if (midpoint % 2)
{
size = midpoint;
}
else
{
a += midpoint;
size -= midpoint;
}
}
}
return result;
}
On Aug 24, 4:49 am, atul purohit gonewiththe...@gmail.com wrote:
Hi,
A* sorted *integer array contains elements in pairs. All the pairs are
complete except one element whose pair is missing. Find that element.
Ex. { 1,1,2,2,2,2,3,3,4,5,5}
result = 5
There is a standard solution which returns an XOR of all the elements.
But
this needs O(n) time complexity. The person who asked me this question
said
that this can be done in O(n). Maybe we can eliminate some elements.
Anyone knows how to do this?
Cheers,
Atul
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
