Solution to Missing-Integer by codility

28 Jul

Question: https://codility.com/demo/take-sample-test/missing_integer

Question Name: Missing-Integer or MissingInteger

83 Replies to “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?
        Thanks

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

    Result:
    https://codility.com/demo/results/demoMSXU28-G6F/

  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:
      O(N**2)
      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%

      • 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

  8. 100% in JS https://codility.com/demo/results/demoWN6DHU-JVT/

  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%:

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

    Here’s the link:
    https://codility.com/demo/results/demoA3WP3K-ZCA/

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

    • 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());

      Let me know your opinion.
      Best Regards

  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:

  17. My solution in javascript

  18. 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))

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

  20. My solution using Google go language

  21. My solution using C++ – 100%

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

  23. My Java Solution 100%

  24. PHP 100%

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

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

  27. This is one easy way based on the edge cases given

  28. This post still comes up so I’ll put my JavaScript solution for keepsake 🙂

    Scores 100% on Task score – Correctness – Performance

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

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

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

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

    But I liked reading about your approach.
    If you can provide a solution for the new problem NOT using sort (which I do) I’d be grateful to see it. 🙂

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

  34. My solution in Python:

  35. Solution in Python 100% :-

  36. This is my c++ solution with 100% performance and correctness

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

Leave a Reply

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

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!