Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive:  Given an array of inte­gers which has all the repeat­ing num­bers (twice) but two num­bers which are non-repeating. Write an algo­rithm to find out those two numbers.

Exam­ple

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

Approaches:

This prob­lem is sim­i­lar to prob­lem “Find two repeat­ing ele­ments in an array”. There could be mul­ti­ple solu­tions like sort the array {O(nlogn)} or use hash map{Time com­plex­ity: O(n) , space com­plex­ity: O(n)}

In this arti­cle we will dis­cuss solu­tion which has time com­plex­ity: O(n) and space com­plex­ity: O(1), con­stant extra space.

Use XOR: time com­plex­ity: O(n) and space com­plex­ity: O(1)

  • Let’s say non-repeating ele­ments are X, Y.
  • A XOR A = 0
  • XOR all the ele­ments of array. This will can­cel 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:

Out­put:

Non Repeating Elements are: 2 and 8

You may also like...

  • San­tanu Sahoo

    if the rep­e­ti­tion is odd times, your logic fail then.
    try with input {2,3,1,3,2,7,3}

    • tuto­ri­al­hori­zon

      Thanks for point­ing it out, will cor­rect the objec­tive of the question