1) Given an array of numbers where each number has a duplicate except one, write a program to return the lone number.

Question

William Wu · Accepted Answer

Solution 1
Use a bit map for all possible numbers.
Initialize it with all 0.
traverse the array and XOR the corresponding bit for each number.
in the final bit map, the bit with 1 corresponds to the lone number. O(n)
 Solution 2
Sort the array, then traverse it. O(n log n), but less memory.

vp · Answer

u can just XOR all the numbers..the result is the lone number

Sigiloso · Answer

XORing the numbers won't work if there are numbers that occur an odd number of times. So if your array is [1, 3, 3, 2, 2, 2] XORing the array will return 1 XOR 2.

Sigiloso · Answer

The question states that each number has a duplicate so there cant be 2 numbers that occur odd number of times. There can only be 1 lone number, which is why XOR will work.

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas