Competitive Coding - Editorial 1

Today I will introduce you all with my competitive coding skills which are like my passion or one can say it as passion only, obviously because I like it in the first place and another, I even like solving number theory puzzles which include intensive Mathematics. So without any further due let's dive into one of the Google Interview Question according to Coding Mafia (Online platform to learn competitive programming).

Question:-

Given an array of numbers in which each number comes twice except for 2 numbers. Find these two unique numbers.

Time:O(n)

Space:O(1) - [Except for Input Array]

Testcase 0:

Input : [1, 2, 2, 1, 3, 5]

Output : 3 5

Note: Before directly seeing an explanation I strongly recommend you to think on your own at first and then go for an explanation. Directly seeing an explanation can create harm to you and not to me.

Concepts Used:

Bitwise Operation, Elementary Algebraic Operation

Explanation:

STEP 1: Doing bitwise XOR of all the numbers.

Reason: As every number in an array is repeating itself twice except for 2 unique numbers which we are to find and also XOR of 2 same numbers equals 0 which clearly states that XORing of all numbers in an array will leave you with a number which contains an answer to XOR of 2 unique number which we are about to find.

For e.g. array = [a, b, b, a, c, d] here a, b, c, and d are any of the positive numbers.

(In case if anyone doesn't know then '^' represents bitwise XOR)

XOR of all of them = a ^ b ^ b ^ a ^ c ^ d

= (a ^ a) ^ (b ^ b) ^ (c ^ d) (Grouping same number)

= 0 ^ 0 ^ (c ^ d)

= c ^ d

OverallXOR = c ^ d (Named it for future referencing)

STEP 2: Find a number such that XORing it with OverallXOR will leave you with a number which again XORing with OverallXOR gives you previously taken number.

Taking previous e.g. OverallXOR = c ^ d

Now run a for loop through all the array numbers and choose a number that satisfies the above-stated condition.

Suppose our for loop comes across 'c' in an array so XORing it with OverallXOR will give you

tmp = c ^ (OverallXOR)

= c ^ (c ^ d)

= (c ^ c) ^ d (Grouping same numbers)

= d

Now XORing resultant number with OverallXOR must give us 'c' (previously taken number):

FinalResult = d ^ (OverallXOR)

= d ^ (c ^ d)

= (d ^ d) ^ c (Grouping same numbers)

= c

Hence we are getting previously taken number 'c' so one can take 2 such unique numbers.

STEP 3: Divide the OverallProduct (Product of all the numbers in an array) by two numbers found by the above step must give us a number which is perfect square root.

Reason: Above process can sometimes leave you with 2 wrong unique numbers so it is an extra step for ensuring that you have found correct unique numbers.

OverallProduct is given as below

Then dividing below by 'cd' will give you a number which is perfect square root.

So check for following in code.

if ((squareRoot(OverallProduct)/product of 2 unique numbers) is integer) then

chosen 2 numbers are perfectly correct.

And hence you have achieved your final task.

I think this is the most optimum solution and the most correct solution that I have came across so far. If you think I am wrong at any point or if you are able to crack it with some another way then do let me know, you can always contact me. You can obviously ask me in case of any doubt in an above-stated explanation.

Till then peace out :)

In case of any kind of implementation problem do check out the below provided link.

solution in C++