0

There are 1Billion numbers from 1 to 1Billion but there is one number missing. They are all randomly available, how will you find the missing one in best possible way.

  • randomly available means are they randomly distributed throughout the array (i.e. 5984,1,10937658, 20 ...)
Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
Supriya
  • 1
  • 1
  • What does "randomly available" mean? Are they in an array? Are the numbers in sequence (i.e. 1,2,3,4,...), or are they randomly distributed throughout the array (i.e. 5984,1,10937658,...)? – Jim Mischel Apr 22 '11 at 16:29
  • Your question is not well specified. Perhaps this http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-number will help. – Jim Mischel Apr 22 '11 at 19:23
  • As the question I linked above says, the sum of numbers from 1 to N is `((N^2)+N)/2`. So if you know that the numbers are from 1 to 1 billion, with one missing, you just sum them, subtract the sum from the expected number, and that's your missing number. – Jim Mischel Apr 23 '11 at 19:23

2 Answers2

1

These are only theoretical considerations,but if the numbers are sorted 1,2,3...1B so you just can split your number group into to parts 1 ... 0.5B and 0.5B ... 1B then check how much elements are in first group: if there are less than 0.5B elements thats means missing value is between 1 and 0.5B, if there are 0.5B elements thats means missing value is between 0.5B and 1B. Go ahead with the process until you find the missing value.

I do not know whether this is a very quick way, but it is certainly faster than checking each value :D

Maybe it puts you on the road

Tomas
  • 333
  • 1
  • 15
1

If limited memory is concern, Start XORing each number from initially. Then XOR with 1 to 1B. The number that will remain is the missing number.

Something like this:

Input-1 XOR Input-2 XOR Input-3 XOR Input-last XOR ... XOR 1 XOR 2 XOR...XOR 1B.

If you have ample of memory, sort all numbers and search sequentially.

First one is O(N) while second one is O(NlogN)

Smaller set example: 

1 xor 3 xor 1 xor 2 xor 3 => 2
Jack
  • 1,398
  • 3
  • 16
  • 26
  • I don't know why you would ever want to sort (`Ɵ(N)` space, `Ω(N) ∩ O(N log N)` time) if you could use the very elegant and fast XOR trick (`Ɵ(1)` space, `Ɵ(N)` time). –  Nov 11 '15 at 23:13