# Solution to Missing-Integer by codility

28 Jul

Question Name: Missing-Integer or MissingInteger

### 82 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

• Dan says:

Although your solution is valid (tested in ruby console):

It’ll not work on the `Codility` challenge because as of Ruby 1.9.0, String#s are no longer Enumerable. You can’t simply iterate over a String or convert it to an Array

• 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.

• Jude says:

Hi Ben,

I’m new to python programming.

Can you explain to me how you came up with your answer?

• Simply genius

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.

• Nico says:

Hi, I came to this answer 5 years later!
I change this line:
max = Math.max(max, length); // taking into account arrays with random elements

with this:
max = Math.max(max, positives.size());

Best Regards

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:

27. pio says:

28. kswan says:

My Java Solution 100%

29. Stuart De Usoz says:

PHP 100%

30. Stuart De Usoz says:

Javascript 100% (however, both this and my previous PHP version even though scoring 100% show Detected time complexity: O(N) or O(N * log(N)) SO next I’m going to study that pidgeonhole principal.

31. smog says:

32. Damilola I Dare-Olipede says:

33. Luiz says:

If someone is looking for a java solution can try it (100% in both correctness and performance)

34. droid says:

This is one easy way based on the edge cases given

35. This post still comes up so I’ll put my JavaScript solution for keepsake ðŸ™‚

Scores 100% on Task score – Correctness – Performance

36. pabhio@o2.pl says:

37. pabhio@o2.pl says:

Hi, how performance of function set() does look like? Is it much faster compare to single for loop with list or dict as a help?

• Sheng says:

I cannot see why it’s working. The problem asks for a single integer, while your code returns a dictionary.

38. JT says:

100% on codility but time complexity O(N) or O(N*log(N))

Not heard of the pigeon hole but now going to look into it.

39. Yussuph Ibitoye says:

40. Jackie Ma says:

My solution. I thought the time complexity should be O(N), Why it says it is O(N**2)?

• Sheng says:

Because of the `not in` operation.

41. Schantall says:

This hasn’t been updated in a while… just FYI in case you were confused reading the solution:
The question has changed and now in the array there aren’t only integers between 1 and N allowed, it’s *any* N integers between 1 and 100000.
The pidginhole therefore won’t work anymore.

If you can provide a solution for the new problem NOT using sort (which I do) I’d be grateful to see it. ðŸ™‚

42. 100% solution using Swift – I do not fully understand the Pinghole principle but it works!

43. Arthur says:

My solution in Python:

44. NITESH JAISWAL says:

Solution in Python 100% :-

45. Achref Ben Brahim says:
46. Jay Bariya says:

100% on correctness and performance. Detected Time Complexity – O(N) or O(NlogN). I’ve explained my code with comments.