A solution is to sort the array taking advantage of the fact that if the contents are in fact a permutation of the values 0..n-1, value x always goes in position A[x]. Therefore you can immediately swap value x into the correct position. If that position already contains value x, you have identified a duplicate.
bool hasDuplicate(int *a, int n) { for(int i = 0; i < n; ++i) { while(a[i] != i) { int j = a[i]; if (a[j] == j) return true; a[i] = a[j]; a[j] = j; } } return false; } At first it may appear to be O(n^2) but notice that each pass through the inner loop puts one value in its correct place. Thus the inner loop executes at most n times. Unlike a similar solution above, if it finds a duplicate it immediately returns, so in some cases it doesn't require n iterations. This solution is also faster than the solution using the sign bit, based on a benchmark test I ran. Don On Oct 30, 2:27 pm, Don <dondod...@gmail.com> wrote: > Given an array of N integers in the range 0..N-1, determine if any > number is repeated in the array. > Solution should execute in O(n) time and use constant space. > Don -- 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.