CODEWITHSUNDEEP
algorithm
KingKongFrog
KingKongFrog

Reputation: 14419

Most efficient way of finding missing integer in array

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?

Upvotes: 1

Views: 1008

Answers (2)

Martin Zikmund
Martin Zikmund

Reputation: 39082

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.

Upvotes: 10

Kartik
Kartik

Reputation: 9853

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

Upvotes: 3

Related Questions