Find two non-repeating numbers in an array in O(n) time and O(1) space

by

Objective:  Given an array of integers which has all the repeating numbers (twice) but two numbers which are non-repeating. Write an algorithm to find out those two numbers.

Example

int [] arrA = {4,5,4,5,3,2,9,3,9,8};
Output: 2 and 8

Approaches:

This problem is similar to problem “Find two repeating elements in an array”. There could be multiple solutions like sort the array {O(nlogn)} or use hash map{Time complexity: O(n) , space complexity:  O(n)}

In this article we will discuss solution which has time complexity: O(n) and space complexity: O(1), constant extra space.

Use XOR: time complexity: O(n) and space complexity: O(1)

  • Let’s say non-repeating elements are X, Y.
  • A XOR A = 0
  • XOR all the elements of array. This will cancel all the repeated elements.
  • Result will be X XOR Y, since only X and Y are not repeating.
  • 1 XOR 1 =  0 and 1 XOR 0 = 1 with this logic in the result of X XOR Y if any kth bit is set to 1  implies either kth bit is 1 either in X or in Y not in both.
  • Use the above step to divide all the ele­ments in array into 2 groups, one group which has the ele­ments for which the kth bit is set to 1 and sec­ond group which has the ele­ments for which the kth bit is 0.
  • Let’s have that kth bit as right most set bit (Read how to find right most set bit)
  • Now we can claim that these two groups are respon­si­ble to pro­duce X and Y.
  • Group –1: XOR all the ele­ments whose kth bit is 1 will pro­duce either X or Y.
  • Group –2: XOR all the ele­ments whose kth bit is 0 will pro­duce either X or Y.
  • See the image below

 

Code:


public class TwoNonRepeatingXOR {
public void find(int [] arrA){
//xor will the xor of two non repeating elements
//we know that in a XOR b, any particular bit is set if that bit is set in either a or b
//we can use this to divide the array elements into two groups where each group will be responsible
// to get a and b
int xor = arrA[0];
for (int i = 1; i <arrA.length ; i++) {
xor ^= arrA[i];
}
//get the right most set bit
int right_most_set_bit = xor & ~ (xor –1);
//divide the array elements into 2 groups
int a=0,b=0;
for (int i = 0; i <arrA.length ; i++) {
int x = arrA[i];
if((x & right_most_set_bit)!=0)
a ^= x;
else
b ^= x;
}
System.out.println("Non Repeating Elements are: " + a + " and " + b);
}
public static void main(String[] args) {
TwoNonRepeatingXOR t = new TwoNonRepeatingXOR();
int [] arrA = {4,5,4,5,3,2,9,3,9,8};
t.find(arrA);
}
}

view raw

TwoNonRepeatingXOR.java

hosted with ❤ by GitHub


Output:

Non Repeating Elements are: 2 and 8

Related Posts: