This post is completed by 2 users

Add to List 
Find two nonrepeating numbers in an array in O(n) time and O(1) space
Objective: Given an array of integers that has all the repeating numbers (twice) but two numbers that are nonrepeating. 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 the 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 a solution that 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 nonrepeating elements are X, Y.
 A XOR A = 0
 XOR all the elements of the array. This will cancel all the repeated elements.
 The 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 the array into 2 groups, one group which has the elements for which the kth bit is set to 1 and a second group which has the elements for which the kth bit is 0.
 Let’s have that kth bit as the rightmost set bit (Read how to find right most set bit)
 Now we can claim that these two groups are responsible for 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:
Output:
Non Repeating Elements are: 2 and 8
Also Read: