Codility ‘PermMissingElem’ Solution

Short Problem Definition:

Find the missing element in a given permutation.

Link

PermMissingElem

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1)

Execution:

Sum all elements that should be in the list and sum all elements that actually are in the list. The sum is 0 based, so +1 is required. The first solution using the + operator can cause int overflow in not-python languages. Therefore the use of a binary XOR is adequate.

Solution:
def solution(A):
    should_be = len(A) # you never see N+1 in the iteration
    sum_is = 0

    for idx in xrange(len(A)):
        sum_is += A[idx]
        should_be += idx+1

    return should_be - sum_is +1

def solution(A):
    missing_element = len(A)+1
    
    for idx,value in enumerate(A):
        missing_element = missing_element ^ value ^ (idx+1)
        
    return missing_element

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Sasha Shipka

    My solution:

    solution(A):
    # write your code in Python 2.7
    return set(range(1, len(A) + 2)).difference(set(A)).pop()

    Got:

    Code: 22:16:03 UTC,final, score: 100.00

    Detected time complexity:
    O(N * log(N)) or O(N)

    • Hey Sasha,

      your solution is about ~ 3*N + some additional space complexity O(N). Good to know that it passes the tests. It is conceptually easier to understand.

      • Sasha Shipka

        Hi, I know, that’s why I pasted complexity 🙂 I saw several optimal solutions in terms of computer speed. I try to be as simple as possible and with smallest amount of code and effort. Also easy to maintain. Human work is much more valuable.
        Consider real life coding. We never need to find optimal solution in terms of speed unless that part of code is actual bottleneck. When it is we try to find it, otherwise we keep code good for human beings. Otherwise programming would never leave asm languages.
        I find these tests fun like brain puzzles and refreshing for university knowledge computer science concepts. I checked out some other test, they are indeed a challenge and if I catch time perhaps I’ll try to solve them too in this manner.
        I found about this problems when I got job offer which requires to do those problems as preliminary test. The approach which turns on all red lights about sanity. The offer I would delightfully decline any time and have good feeling and smile whole day.

        • For your second part: have you read Atwoods classic http://blog.codinghorror.com/why-cant-programmers-program/ ? In terms of coders, there are too many out there that can not solve the most trivial of questions. How would you expect them to solve harder tasks on their own? I would not put an offer down, because they gave me a trivial question (unless I am known for my work, or it is a senior position…). If you have some other portfolio, that can prove your coding abilities, I do not think that anyone should subject a candidate to the process.

          I agree completely, that time == money and you should program as effectively as possible (that is why I use python, no time/energy to loose time with C++). Yet, when you take the time to do challenges, do you not want to learn new tricks?

          Sometimes I intentionally write more complicated code (more lines of code) to make the idea more clear. Smart code that is compressed to too few lines can be hard to understand. Or, sometimes, much easier, as with the other one you posted here 🙂

          • Sasha Shipka

            Nice article, I’ve met some of those examples, although not so extreme as pointed there. They just come and go. I also met some companies who see humans as intelligent livestock. As simple tests can be qualifiers for programmers, admission procedures can qualify them. They also just come and go. Pure Zen.
            I enjoy solving coding puzzles. Also I enjoy fixing my bike. Actually, I have one in my garage which needs fixing. If some of their managers comes and fix it tonight, I may reconsider the offer, … maybe, some other time.

  • Hey Sasha,

    your solution is about ~ 3*N + some additional space complexity O(N). Good to know that it passes the tests. It is conceptually easier to understand.

  • Richard Yang

    I don’t know why I get an overflow when I use Java.
    Actually, when the size of the array is 100,000, it should not cause overflow. But the codility reports wrong answer when large range.

    • Are you counting all elements in an array? Are you creating a sum?

      Are you sure it is an overflow?

      The sum of as much as 2 elements can cause an overflow.

  • artisdom

    C version:

    #include

    int solution(int A[], int N)
    {
    int i, ret = 0;

    for (i = 0; i < N; i++) {
    ret += (N + 1 - i) - A[i];
    }

    ret += 1;
    return ret;
    }

    int main(int argc, char *argv[])
    {
    int i, N = 100000, A[N], ret = 0;

    for (i = 0; i < N; i++) {
    A[i] = i + 1;
    }

    A[N - 1] = 100001;
    ret = solution(A, N);
    printf("solution: %dn", ret);
    return 0;
    }

    • hey Artisdom,

      I reformatted your code 🙂

      You are right, one variable is enough.

      • artisdom

        Very nice, don’t know that’s supported in the comments.

  • Abhijeet Dahat

    Check my solution. It is giving 100% performance.

    https://codility.com/demo/results/trainingXN85A8-74V/

    or

    long length = A.Length;

    length = (length+1)*(length+2) / 2;

    for (int i = 0; i < A.Length ; i++)

    {

    length = length – A[i];

    }

    return (int)length;

  • Nico
  • Mostafa Ahmed

    I write this in java
    public static int solution(int[] A) {
    return IntStream.rangeClosed(0, A.length+1).sum() – IntStream.of(A).sum();
    }

  • Omar Ibañez

    My solution without loops

    def solution(A):
    complete = (len(A)+1)*(len(A)+2)//2
    incomplete = sum(A)
    return complete – incomplete

  • Adi

    C# solution:

    public int solution(int[] A)
    {
    long arrSum = 0;

    for (int i = 0; i < A.Length; i++)
    {
    arrSum += A[i];
    }

    //Used arithmetic sequence sum formula, can use a for loop instead
    decimal seqSum = ((A.Length+1m)/2)*(((A.Length +1) - 1) + 2);

    return Convert.ToInt32(seqSum-arrSum);

    }

    C# XOR solution:

    public int solution(int[] A)
    {
    int result = 0;

    foreach (int elem in A)
    {
    result ^= elem;
    }

    for (int i = 1; i <= A.Length+1; i++)
    {
    result ^= i;
    }
    return result;
    }

  • Chima Alaebo

    JavaScript solution
    function solution(A) {

    var total = 0

    var total1 = 0

    for ( var i = 1; i <= A.length + 1; i++ ) {

    total += i

    }

    for ( var i = 0; i < A.length; i++ ) {

    total1 += A[i]

    }

    return total – total1

    }

  • Rama Moorthy

    GO Code:
    package main

    func Solution(A []int) int {
    n := len(A)
    total := (n+1)*(n+2)/2;

    for i := 0; i< n; i++ {
    total -= A[i];
    }
    return total;

    }

  • Siavash Goudarzi

    PHP:

    function solution($A) {
    $complete = range(0,count($A));
    return array_sum($complete) + count($complete) – array_sum($A);
    }