1

An Array A contains n-1 unique integers in the range [0,n-1], that is , there is one number from this range that is not in A. Design an O(n) algorithm for finding that number. You are allowed to use only O(1) additional space besides the array A itself.

Anyone can help?

Sklivvz
  • 30,601
  • 24
  • 116
  • 172
Anqi Zhang
  • 27
  • 1
  • 7

2 Answers2

3

Sum up the numbers from from 0 to n-1 and then find the sum of the array and the missing number is sum - sum of array

Explanation: sum if 0+1+2+...+n-1 and the array has all these numbers too except one so when you add to 0+1+2+...+n-1 all the numbers in the array with a "-" prefix, each number will cancel his "+" counterpart and so you will be left with the "+" who has no counterpart in the array and so this is the missing number

NOTE: storing a number is log(n) bits but in most places (that I have seen) they dont talk in bit resolution and storing a number is O(1) space, so it depends on how it is defined in your question

tomer.z
  • 1,033
  • 1
  • 10
  • 25
  • 1
    It is noteworthy to mention that adding `n` integers does not take a constant space, but rather a `log(n)` space. The number of bits required for representing the number `n` is `log2(n)`. – Adam Matan Sep 11 '14 at 10:25
  • It depends what you consider as space complexity, from what I know storing a number is O(1) but you are right, it depends on how it is defined in the question – tomer.z Sep 11 '14 at 10:33
  • Great. That's the reason you should be careful with this one as an interview question. If you don't take a closer look into it, you might look like a fool if a smart candidate shows up. – Adam Matan Sep 11 '14 at 10:36
  • That's a nice answer. I have a little bit of improvement though. The improvement is when the missing number is zero. Your algorithm won't detect it. The solution to this problem is by adding 1 (or call it shifting by 1) to each number in both (the array and the range). Hence, the new algorithm to solve the problem is: `summationOfRange = n(n+1)/2; summationOfArray = n - 1 + sum(array); missingNumber = summationOfRange - summationOfArray - 1;`. That's all. – joker Feb 01 '16 at 17:31
0

Given lists a(size 100) and b(size 99) of unique integers in range 0-99 with random ordering. 

a = RandomSample[Range[0, 99]]
b = Take[RandomSample[Range[0, 99]], 99]

Find missing element in b.

element = Total[a]-Total[b]

Language used is Mathematica.

Margus
  • 19,694
  • 14
  • 55
  • 103