Given an array from 0 to n integers containing values 1 through n, write a method that can find any duplicate and return it (note there must be at least one duplicate because of there being more indices than available values). Write a method with "good" running time and space complexity.

Question

Given an array from 0 to n integers containing values 1 through n, write a method that can find any duplicate and return it (note there must be at least one duplicate because of there being more indices than available values).  Write a method with "good" running time and space complexity.

Nick S · Accepted Answer

A really neat way to solve this is by doing some math and figuring out 1 + 2 + ... + n = (n+1)*n/2.

So what you can do is make a pass through the array and sum up all the values and then subtract the sum from 1 to n and return that value. Or in psuedocode:


for i=0 to n:
  sum += list[i]

return sum - n * (n+1) / 2

freeshell74 · Answer

You can either sort, or you can divide the set into two sets first according to the last bit (0 or 1), and then further split the two sets into four sets according to the second bit (0 or 1) ... It would be more efficient than sorting. Its complexity is just O(logN), since there is no comparison and we don't care about the order (we only care about duplicates)

Sigiloso · Answer

Possibly consider sorting the input, create a hashing of the values, etc. However, prefer linear time solution.

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas