Solution to Missing-Integer by codility

28 Jul


Question Name: Missing-Integer or MissingInteger

44 thoughts on “Solution to Missing-Integer by codility

  1. 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:

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

    The same solution ported to Python

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


  3. Here is my solution, following “Pigeonhole principle”:


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


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

  5. Bad solution (Pascal)

    • It is bad because of the time complexity:
      It got a 100% for Correctness and a 25% for Performance. So it’s a fail

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

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

  7. Ruby 100%

  8. 100% in JS

  9. – 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)

  10. This is my python solution for 100%:

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


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

    Here’s the link:

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

      A = [3, 4, 6];

      return 5 instead of 1?

      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?

  12. Another JS solution this one works 100% 🙂

  13. Solution in C#:

  14. 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?

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *