1

I'm aware of the XOR trick to find the non-repeating element in a sorted array (which has been asked before):

public int singleNumber(int[] nums) {
    int result = 0; 
    for (int i = 0; i < nums.length; i++) {
        result = result ^ nums[i]; 
    }
    return result; 
}

But how can we use the same logic to do the opposite?

More specifically: Consider a sorted array where each element but one occurs only once, how do we find the one element that repeats in O(1) space?

Fiery Phoenix
  • 1,156
  • 2
  • 16
  • 30
  • Possible duplicate of [In less-than-linear time, find the duplicate in a sorted array](http://stackoverflow.com/questions/9673658/in-less-than-linear-time-find-the-duplicate-in-a-sorted-array) – Yogev Levy Jan 23 '17 at 06:51
  • `Consider a sorted array where **each element but one occurs only once**, how do we find the one element that repeats` isn't this statement a contradiction? – Trash Can Jan 23 '17 at 06:54
  • Not an exact duplicate, but the "simple linear search" mentioned in the other post would work. – Henry Jan 23 '17 at 06:54
  • Is the difference of nth, (n+1)th element is same through out ?? – Srikanth Balaji Jan 23 '17 at 07:15
  • I posted my own solution. I overthought the issue because I was looking for an XOR-based solution, but I couldn't figure that out. – Fiery Phoenix Jan 23 '17 at 07:48
  • You do realise that this "XOR trick" only works if the repeating numbers occurs an even number of time (since it needs two occurence for the XOR to cancel the value). – AxelH Jan 23 '17 at 07:53

3 Answers3

1

The XOR trick is only neat if you want to discard even numbers of repetitions. One way of looking at it is to say that the xor of all the elements of an array is the xor of the oddly-repeating elements of that array; so that, if there is only one oddly-repating element, you can find it in that way. And you do not need the array to be sorted at all to do so:

// could also have called it xorOfOddlyRepeatingIntsInArray(int[] a)
public static int findSingleNonEvenlyRepetingIntInUnsortedArray(int[] a) {
  int x = 0;
  for (int i: a) x ^= i;
  return x;
}

For what you are asking, both of these fragments find the repeat element in a sorted array in O(1) space and O(n) time:

public static int findSingleRepeatingIntInSortedArray1(int[] a) {
  for (int i=0; i<a.length-1; i++) if (a[i] == a[i+1]) return a[i];
  return -1;
}

public static int findSingleRepeatingIntInSortedArray2(int[] a) {
  for (int i=0; i<a.length-1; i++) if ((a[i] ^ a[i+1]) == 0) return a[i];
  return -1;
}

But you should prefer version 1, as a[i] == a[i+1] is much more readable than (a[i] ^ a[i+1]) == 0, or (a[i] - a[i+1]) == 0, or (a[i] & a[i+1]) == a[i], or other arcane variants to check for equality. Xor buys you nothing in this case.

For laughs and giggles, this code finds the single repeating value in O(1) space in an unsorted array:

 public static int findSingleRepeatingIntInSortedArray3(int[] a) {
    for (int i=0; i<a.length; i++) {
       for (int j=i+1; j<a.length; j++) {
          if (a[i] == a[j]) return a[i];
       }
    }
    return 0;
 }

Yes, it is O(n^2) time, and there are faster ways of finding the first repeated element (sorting comes to mind) - but it is a valid answer to the question.

tucuxi
  • 17,561
  • 2
  • 43
  • 74
0

I think someone removed the comment which was using XOR. Here it is:

    private int returnNumber(int[] nums) {
    int result = 0;
    for (int i = 1; i < nums.length; i++) {
        if ((nums[i] ^ nums[i - 1]) == 0) {
            result = nums[i];
            break;
        }
    }
    return result;
}

I am really not sure if this uses O(1) or not.

Apoorv Karkare
  • 89
  • 4
  • 1
    if the space (memory) required by your function does not grow with the size of the input (in this case, the number of elements in `nums`), then your algorithm is in O(1). Since regardless of `nums.length` you are always using the same extra space (for `i`, `result` and, depending on platform/compiler/java internals, storing intermediate calculations) - your code is O(1) – tucuxi Jan 23 '17 at 11:37
-1

I did not manage to find an XOR-based solution, but this surprisingly simple solution does the trick in-place. 

public static int getRepeatingValue(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) {
            return nums[i]; 
        }
    }
    return -1; 
}
Fiery Phoenix
  • 1,156
  • 2
  • 16
  • 30