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 elements in array into 2 groups, one group which has the elements for which the kth bit is set to 1 and second group which has the elements 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 responsible to produce X and Y.
- Group –1: XOR all the elements whose kth bit is 1 will produce either X or Y.
- Group –2: XOR all the elements whose kth bit is 0 will produce 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); | |
| } | |
| } |
Output:
Non Repeating Elements are: 2 and 8
if the repetition is odd times, your logic fail then.
try with input {2,3,1,3,2,7,3}
Thanks for pointing it out, will correct the objective of the question