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
-- 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.