1

Given an array of integers 1 to 100 (inserted randomly), and one integer is taken out of the array. What is the most efficient way of finding the integer that is missing?

KingKongFrog
  • 13,946
  • 21
  • 75
  • 124
  • 3
    possible duplicate of [Quickest way to find missing number in an array of numbers](http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-an-array-of-numbers) – baci Jan 12 '14 at 21:46
  • At 2.8k rep, one would kind of expect a user to know to show proof of a bit of research done in a question... – Bernhard Barker Jan 12 '14 at 23:14

2 Answers2

10

As you know the integers, make a sum of all of them:

(1+N)*N/2 = (1+100)*100/2 = 5050

And now substract the sum of those that are in the array (S'). The difference will be the one missing number you seek (so x = 5050 - S').

Time complexity is O(N) and can't be solved faster, because you definitely need to read the array once.

Martin Zikmund
  • 38,440
  • 7
  • 70
  • 91
  • 1
    this is probably not optimal answer , considering N is very large , so you can have an overflow. – Aseem Goyal Jan 13 '14 at 06:34
  • It is optimal, because we are talking about 1..100 range here. In case we got larger nunmbers, we still could use this but implement our own integer class for large integers based on arrays. – Martin Zikmund Jan 13 '14 at 10:11
3

MZetko already answer the basic case but here are 4 other solutions to this where the array can be sorted or unsorted

https://github.com/KartikTalwar/Algorithms/blob/master/Arrays/Find%20only%201%20missing%20number%20from%20an%20array/Find1MissingElementFromArray.py

Kartik
  • 9,463
  • 9
  • 48
  • 52
  • 3
    Rather than just providing a link, [it would be preferable](http://meta.stackexchange.com/a/8259) to include the essential parts of the answer here, and just provide the link for additional reference. If you're not up to this task, you should consider simply [leaving a comment](http://stackoverflow.com/privileges/comment) on the question instead of posting an answer. – Bernhard Barker Jan 12 '14 at 23:14
  • Will keep that in mind the next time, but in my defense, I wrote the answer in the link – Kartik Jan 12 '14 at 23:16
  • Remember that posts are here for the long haul - don't just write new posts to conform to guidelines, but also edit existing ones (i.e. this post). – Bernhard Barker Jan 12 '14 at 23:20
  • What's worse when the link is now a 404 – Yaobin Then Nov 29 '18 at 10:10