CODEWITHSUNDEEP
arraysduplicatesoperatorsbitwise-operatorsxor
Bugaboo
Bugaboo

Reputation: 971

Given an array of integers, where every number appears thrice except one number appears twice, find the number that appears twice?

This is a problem from "Elements of programming interview". I saw this problem posted here but the accepted answer (or other answers) are not complete.

Using an XOR like operation that works on base 3 systems (which is called xor3 in the post), you get the result which is x xor3 x. However, the problem is to get x. xor3 is defined as addition modulo 3 (where numbers are represented in base 3 system)

How do we get the x portion out of x xor3 x?

Upvotes: 1

Views: 707

Answers (1)

jayesh
jayesh

Reputation: 76

What if you go through the array of numbers once again? Lets say the value that you have after the first iteration is a = x xor3 x

Iterate through all the entries in the array, and xor3 each value with a.

for y in arr:
    if y xor3 a == 0:
        print y
        break
    else
        continue

For now I think this is the naive solution. This is still O(n) considering each xor3 as O(1) with O(1) memory.

Upvotes: 1

Related Questions