# Solution to Missing-Integer by codility

28 Jul

Question Name: Missing-Integer or MissingInteger

### 55 Replies to “Solution to Missing-Integer by codility”

1. Stefano says:

Hi!
Here is a shorter version:

it is not clear from the problem description wether the elements of the array must be <= N.
In case they can take any value within the range it can be changed to:

• Sheng says:

Thanks for sharing you solutions!

Here, the set should works the same as frozenset, right?

• gt says:

Hi, I think this solution is wrong. If I pass A = [99999999], I get 100000000. Answer should be 1

• Sheng says:

Yes, you are right. The solution has bug. Please try to replace “start = 0 if smallest < len(a) else smallest" with "start = 0".

2. Stefano says:

Yep, set and frozenset works exact same way, frozenset is immutable.

• Sheng says:

Great! THX!

3. Hi, here is my solution in PHP 100/100

The same solution ported to Python

• Sheng says:

Hi Ricardo, your solution is right. But the expected worst-case time complexity is O(N). In your solution, you sorted the input array first, which is O(NlogN).

PS: to post the code, please include your code inside a pre block, instead of code block, like <pre> code </pre>

• Thanks for letting me know it Sheng,

When I started the exercise I was concerned about sorting the array (as a small developer, Big-O notation never was my biggest concern, until now) but then I got surprised by the result on Codility. They detected a time complexity of O(N).

Do you know why is that?

For sort() PHP uses a variation of Quicksort, so shouln’t be O(NlogN) as you stated?

Thanks

• Sheng says:

For the general sorting algorithm in practice (http://en.wikipedia.org/wiki/Sorting_algorithm), the bese worst-case complexity is O(NlogN).

logN is small even with a big N. And Codility’s detection is not exactly accurate, and gave you a wrong estimation here.

Thanks for visiting my site! And enjoy coding and photography!

• Sheng says:

By the way, your photoes are amazing! I love them!

• Thanks, I love photography for as long as I can remember ðŸ˜€

4. Gourav says:

Here is my solution, following “Pigeonhole principle”:

5. Ivan says:

Hi,

Thanks for posting your solution. I learned something new from this one. Just wanted to share an opinion: I know that complexity is expressed based on the worst case scenario, but statistically I think that a solution that sorts the array first will almost always be faster. And that’s of course if we assume that the input is an array of random (or seemingly random) numbers, not someone deliberately creating worst case scenarios.

So if we do something like this:
1. sort the array,
2. go through the sorted array (ignoring negative values)
2.1. check if the first positive element is greater than 1, i which case just return 1, which leaves just the sort complexity O(logN), and that’s most cases when dealing with random input
2.2. otherwise look for the first gap (between positive numbers), which, in the case of random input will most probably be very early in the array, giving O(logN) + O(small fraction of N)

So if we were to solve a real world problem, we would probably inspect the input statistically (maybe even ad-hoc, using intuition) and then choose the solution that works the best for the specific use. The worst case O(logN)+O(N) would just be a very very rare occurrence.

Best Regards

ðŸ™‚

• Sheng says:

Thanks for your discussion! However, the average performance of the best practical sorting algorithms is O(NlogN), not O(logN). Therefore, your solution does NOT fit the requirements.

6. calinutz says:

• calinutz says:

It is bad because of the time complexity:
O(N**2)
It got a 100% for Correctness and a 25% for Performance. So it’s a fail

7. calinutz says:

Also a bad Pascal solution (same time complexity O(N**2)) score : 100% and 50%
(now sorting the array before doing the calculations)

• Sheng says:

I sincerely appreciate your sharing and involvement. However, to keep the comunity clear, please only post the good solutions. Sorry for that.

8. a131a says:

Ruby 100%

• nicolai says:

Ruby

• No you didn’t, I just test your solution verbatim and it doesn’t work.

• Sheng says:

I also tried minutes ago. It does work.

9. Neil Jones says:

– add up the total of the array (s) and count the number of elements. (n)
– for the full array 1..n+1 the sum would be (1+n+1)*(n+1)/2 i.e. there are n/2 pairs of numbers summing to 1+ (n+1)
– therefore the difference between the expected sum (including the missing element) and the actual calculated sum s is the missing value
– works in O(n)

• Sheng says:

Yes, logically it is right. But it may lead to overflow, which makes the result unreliable.

• Miroslav says:

Are you sure this is ok if the numbers in array are totally random and can be repeating ?

• Sheng says:

It works if and only if the numbers are unique and in range of 1 to N + 1. I was wrong.

10. Ben says:

This is my python solution for 100%:

• Sheng says:

Assuming the hash function is perfect (which is next to being real), the solution is a good exmaple of hash set.

Thanks!

• mark says:

i am learning python. can you please explain how this works?

• Sheng says:

set(range(1, len(a) + 2)) is the set of all elements plus one possible missing integer.
set(a) is the set of all candidates, after dedup.
You could Google and find all these build-in functions.

11. Here my solution in Java 100%, a little bit verbose but it works:

https://codility.com/demo/results/demoA3WP3K-ZCA/

• Pepe says:

How come every solution checks from the 1..N range?
Shouldn’t an array containing:

A = [3, 4, 6];

Also in the problem statement it’s not clear what value to return if the array is complete. How did you guess what they required?

• Sheng says:

The problem statement: returns the minimal positive integer (greater than 0) that does not occur in A.

12. Jovan Damjanovic says:

Another JS solution this one works 100% ðŸ™‚

• Sheng says:

Awesome! However, the variable name “min” is a little bit misleading. It is actually the trying prober for the result.

13. mmcinerney says:

14. Yonni says:

Solution in C#:

15. Jim Bo says:

I don’t understand limiting the size of the occurrence array to N elements.

According to the problem on Codility,
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [âˆ’2,147,483,648..2,147,483,647].

So A might be [2147483647] for example where N=1 and then the A[item..] references would be out of range.

Have I misunderstood the question?

• Sheng says:

It’s pigeonhole principle. With N integers, the minimal missing *positive* integer must be in the range of [1, N + 1] (both ends inclusive).

16. manu says:

Something I dont get is, wouldn’t doing 2 for loops end up being O(2N)?

• Sheng says:

Big O is used to measure the order of complexity. O(2N) means exactly the same thing as O(N).

17. Here is my solution in Python, 100% in both correctness and performance

• Sheng says:

Expected worst-case time complexity is O(N), while yours is O(NlogN) because of the sorting.

18. micropentium6 says:

what if I don’t know pigeonhole principle? O(N) time with O(1) space:

• Sheng says:

reading my blog ðŸ™‚ just kidding

19. nicolai says:

My solution in ruby

20. Che Jansen says:

My solution in javascript

21. Tarandeep Singh says:

in case you need code in JS, ES6.
`A.sort((a,b) => Math.abs(a) - Math.abs(b)).reduce((res, val) => { val === res ? res++ : res; return res; }, 1))`

22. Jose Manuel says:

Here my solution in Java. It works but the time complexity is: O(N) or O(N * log(N))

23. Smith says:

My solution using Google go language

24. Fabio says:

My solution using C++ – 100%

25. doh says:

solution in Ruby for 100%
but
Detected time complexity:
O(N) or O(N * log(N))

26. Ashish Singh says: