[algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
After working on it quite a bit I got an O(log n) algorithm working.
For small cases (size < 10) it sequentially finds the solution.
For larger cases it uses a binary search:
Starting at the midpoint, find the left and the right ends of the
region with values equal to the value at the midpoint. This is done by
another binary search. That gives three regions:
1. Values less than the midpoint value in the left part of the array
2. Values equal to the midpoint value
3. Values greater than the midpoint value in the right part of the
array
One of those regions will be odd in size. If it is region 2, the
midpoint value is the repeated value. Otherwise, narrow the search to
the odd-sized region.
In 1000 trials on an array of size 1001 including a variety of input
data/different sized clumps of equal values, it took on average 7.5
iterations through the main loop and 14 iterations through the inner
binary search loop per call.
Code follows (apologies for how cutting and pasting messes up the
formatting):
// Find left edge of group of equal values including a[midpoint]
int findLeftEdge(int *a, int midpoint)
{
// We know that midpoint > 3. For a small case, just search
sequentially.
if (a[midpoint-4] != a[midpoint])
{
while(a[midpoint-1] == a[midpoint])
--midpoint;
return midpoint;
}
int min = 1; // findSingle eliminates cases where a[0] ==
a[midpoint]
int max = midpoint-4; // Covered by first check above
while(1)
{
int median = (min + max) / 2;
if (a[median] == a[midpoint])
{
if (a[median-1] != a[midpoint]) return median;
max = median-1;
}
else
{
if (a[median+1] == a[midpoint]) return median+1;
min = median+1;
}
}
}
// FInd right edge of group of equal values including a[midpoint]
int findRightEdge(int *a, int midpoint, int size)
{
if (a[midpoint+4] != a[midpoint])
{
while(a[midpoint+1] == a[midpoint])
++midpoint;
return midpoint;
}
int min = midpoint + 4;
int max = size-2;
while(1)
{
int median = (min + max) / 2;
if (a[median] == a[midpoint])
{
if (a[median+1] != a[midpoint]) return median;
min = median + 1;
}
else
{
if (a[median-1] == a[midpoint]) return median-1;
max = median-1;
}
}
}
// 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 if (size < 10)
{
int result = a[0];
for(int i = 1; i < size; ++i)
result ^= a[i];
return result;
}
else
{
// Pick the midpoint of the array
int midpoint = size/2;
// If all values to the left of midpoint are equal, singleton must
be to right.
if (a[midpoint] == a[0])
{
a += midpoint;
size -= midpoint;
if ((size%2) == 0)
{
++a;
--size;
}
}
// If all values to the right of midpoint are equal, singleton must
be to left.
else if (a[midpoint] == a[size-1])
{
size = midpoint;
if ((size%2) == 0) --size;
}
else
{
int left = findLeftEdge(a,midpoint);
int right = findRightEdge(a,midpoint,size);
if ((right-left) % 2 == 0) return a[midpoint];
if (left % 2) size = left;
else
{
++right;
a += right;
size -= right;
}
}
}
}
}
On Aug 24, 4:49 am, atul purohit 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 don
[algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
it is O(n) and complex unnecessary
On Aug 24, 3:58 pm, Ankit Minglani wrote:
> 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 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 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.
[algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
my binary search method in Ruby is similar to Don's. I tested with
array [1,1,2,2,2,2,3,3,9,14,14] , to which the answer should be 9,
and now added what I call "fluff" (meaningless numbers) to either:
the left (300_000 zeroes at the head) , making it difficult for direct
approach; the middle (150_000 of each of the 3's and 14's around
the 9 ); or the right (300_000 18's added to the end). I also had
it run each method 100 times. I just hope the following formats
decently...
user system totalreal
fluff on left
direct 16.75 0.00 16.75 ( 16.753000)
binary0.00 0.00 0.00 ( 0.002000)
fluff in middle
direct8.344000 0.00 8.344000 ( 8.335000)
binary6.844000 0.00 6.844000 ( 6.846000)
fluff on right
direct0.00 0.00 0.00 ( 0.001000)
binary0.00 0.00 0.00 ( 0.003000)
As expected, the direct approach sucks when it hits a large n and the
singleton is near the end. It actually does fairly well otherwise.
By the way, Don, I took "pairs" to mean it divides 2 evenly, and the
asker even gave an example with four 2's. (Assuming his result should
be 4, not 5, typo ;P). So your line about decreasing the midpoint
just once is not enough, and actually to increase binary performance,
a check should be made if ar[mid]==ar[left] , also check if
ar[mid]==ar[right], and if it does, like in my fluff examples , you
can save loads of time on useless checks.
@surender -- good question; I would think no, but binary search would
still return 3. Direct approach would fail with default checks. I
got the impression we were searching for a single[ton].
On Aug 25, 6:32 am, surender sanke wrote:
> { 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 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 wrote:
> > > XOR all the elements, the answer is the number you want.
>
> > > On Aug 24, 5:11 pm, Don 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 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:
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 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 wrote:
> > XOR all the elements, the answer is the number you want.
> >
> > On Aug 24, 5:11 pm, Don 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 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.
[algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
@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 wrote:
> XOR all the elements, the answer is the number you want.
>
> On Aug 24, 5:11 pm, Don 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 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.
[algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
XOR all the elements, the answer is the number you want.
On Aug 24, 5:11 pm, Don 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 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.
[algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
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 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.
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 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 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.
[algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
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 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.
Re: [algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
See interviewer said that it can be done in 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 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 wrote:
>>
>>> @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 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.com>wrote:
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > 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 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
>> algogee
Re: [algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
flag=0; for(int i=0;ihttp://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 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 wrote:
>
>> @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 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.com>wrote:
>> >
>> >
>> >
>> >
>> >
>> >
>> >
>> > > 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 > >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 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, se
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 wrote:
> @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 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.com>wrote:
> >
> >
> >
> >
> >
> >
> >
> > > 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 >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 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.
[algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
@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 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
> wrote:
>
>
>
>
>
>
>
> > 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 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 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
@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 wrote:
> 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 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 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
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 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 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.
[algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
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 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.
