# Codility ‘PermMissingElem’ Solution

##### Short Problem Definition:

Find the missing element in a given permutation.

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.

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

You are right, one variable is enough.

• artisdom

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

• Yes, you have to enclose them in

<code><pre>

• 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

• Sum(A) is a loop ðŸ™‚

• Omar IbaÃ±ez

oh yeah, you’re right.

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]

}

}

• 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];
}

}

• Siavash Goudarzi

PHP:

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

• Matthew Vaughan
• Thomas Sjogren

Using runsum on the expected Array should cut out a bit of time.

def solution(A):
n = len(A)+1
runsum = (n*(n+1))//2
realsum=sum(A)
return runsum-realsum

• Alper Aykac

%100 correctness %80 performance in java
public int solution(int[] A) {

IntStream intA = Arrays.stream(A);
BigDecimal sum = BigDecimal.valueOf(intA.parallel().sum());
BigDecimal lenght = BigDecimal.valueOf(A.length+1);
BigDecimal lenght2 = BigDecimal.valueOf(A.length+2);
BigDecimal iki = BigDecimal.valueOf(2);
BigDecimal sum2 = lenght.multiply(lenght2).divide(iki);

int eksik = sum2.subtract(sum).intValue();