# Solution to Perm-Check by codility

19 Jan

Question Name: PermCheck

This question is a simple variant of the counting question. The Python solution is:

The Java solution is:

### 91 Replies to “Solution to Perm-Check by codility”

1. Henry says:

Hello Shng,
Here is my java version of the PermCheck, but I have an error. I feel, I need to check for one extra condition before the code can work well. When tested with an array like this: int a[] = new int[4,1,3}, it should return 0 but it returned 1. What else do I need to test for to get this code to work perfectly?

• Sheng says:

Please see the update part of my post for the right Java answer. For your answer, the variable “flag” is never used. You would better to remove it. Secondly, you did not use the variable “counter” as it should be. Thirdly, unless the array is sorted, your solution is not working good. Fourthly, even if the array is sorted, the choice of initial value of OccurBefore is not good.

2. Ajeet Singh says:

don’t know why it is missing some part of the code in posting a comment

• Sheng says:

3. Mayank T. says:

Just wanted to add, I did this problem this way and received 100% on performance and accuracy. Apparently the sorted() function works well for this problem.

• Sheng says:

Actually the sorted() function is working well for the test, not for the problem. At least sorted() is O(NlongN). It passed the tests, because logN is small. But the problem requires O(N) solution.

• Sebastian Cheung says:

This also only works for positive numbers right?

• Sheng says:

No. It works for all cases.

• Gerald says:

the code doesnt work properly for A = [1,2] should return 1 not 0

• Sheng says:

It does return 1, which is correct.

• mallesh says:

it is returning only 0’s for all arrays…

• Sheng says:

4. Frank says:

Hi,
I was doing the test today and I found your solution and I saw that you have an error in the solution in the Java code. Suppose you have [4,3,1] as your input array, the length of the array is 3 but when you go into the if statement to check counter[A[i]-1] == 1 –> A = 4 -1 equals 3 and your counter array just have 3 slots (0,1,2) this will give you a wrong index. I also noticed this solution checks for repeated values but it doesn’t check if the permutation has any missing values.

• Sheng says:

First of all, thanks for sharing your idea. But the Java should be right.
On one hand, before we check the counter, we check the index as:
if (A[i] < 1 || A[i] > A.length)
So we are sure that we will get a valid index in the “else if” statement.
On the other hand, with the http://en.wikipedia.org/wiki/Pigeonhole_principle, our solution is right. If N non-repeating integers are in the range [1, N], it MUST be a permutation.

5. Mrigank Mittal says:

we can do the same question by using xor operation:

and its working 100% correct

• Sheng says:

Better than mine! Great solution!
Sorry, even thought it passed all test, it might be wrong. Try [3, 5, 6]

• Kim says:

Yes, XOR does not work. As a matter of fact, I made exactly same mistake as @Mrigank Mittal did. Then why did I take this approach? It’s because I saw the usefulness of XOR in the previous lesson, Perm-Missing-Elem, and I felt that the solution was quite elegant. But this time things were different. So I became curious about what went wrong with XOR. And here is my own answer to the XOR’s limitations.
Assume that we have an array A[] of size N as described.
Firstly, the range of the elements of A[] matters. XOR might work if the range of the elements was [1, …, N], but this time the range is much greater than that, which is [1, …, N + M] where M is an arbitrary positive integer. In this problem where N <= 100,000, N + M can be up to 1,000,000,000. With this situation, a subset of [1, …, N + M] can have an identical XOR summation value even though it is not [1, …, N]. In other words, the uniqueness of the XOR sum is not guaranteed. For example,
1 ^ 2 ^ 3 ^ 4 = 1 ^ 2 ^ 11 ^ 12,
or
0001 ^ 0010 ^ 0011 ^ 0100 = 0001 ^ 0010 ^ 1011 ^ 1100 = 0100.
With this point of view, I eventually realized that XOR is analogous to a parity check, where the checksum is a single bit. So it may detect a single error, but may not a multiple error (maybe one could also represent this as a collision occurred in the hashing). Hence XOR become an unsafe choice when sufficient criteria are not met.
Secondly, things will not be better even if the range of the elements is limited in [1, …, N], because elements in the array are not unique, but can be duplicated. If we have an array of size 6, then
1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 = 1 ^ 2 ^ 2 ^ 4 ^ 4 ^ 6,
or
0001 ^ 0010 ^ 0011 ^ 0100 ^ 0101 ^ 0110 =
0001 ^ 0010 ^ 0010 ^ 0100 ^ 0100 ^ 0110 = 0111,
which demonstrates another failure of XOR operation. In other way, we can say that 3 is modified to 2 and 5 is modified to 4 but these two elements compensate each other so that XOR could not catch the error.
In conclusion, this is another lesson I learned from mistake; the right tool, the right place, the right time.
PS: Is there a way to review my comment before posting, like a sandbox?

• Sheng says:

Awesome explanation! Thank you for the high-quanlity comment!
I will add a plugin for live comment preview.

• Srikanth says:

Question Says the array contains the elements 1 to N.
You have taken the array elements starting from 3.

• Srikanth says:

Question says the array starts with 1. You have taken the first element as 3.

• Sheng says:

No. The question actually says: “A permutation is a sequence containing each element from 1 to N once, and only once.” AND “given an array A, returns 1 if array A is a permutation and 0 if it is not.”

When the input is NOT a permutation, it can start with any number.

6. Emir Kurtovic says:

PHP 100%

• Sheng says:

7. NH says:

Hi there, i think you can reduce the amount of space used in your Java implementation. Right now you have int[] counter but you are only setting 1 value, so you could use a boolean[] counter and accomplish the same thing.

• Sheng says:

Yes, you can use boolean[]. Bitmap works also.

8. Oscar Gonzalez says:

Here is my solution in javascript.

• Sheng says:

9. Sergio says:

Hi there!
I solved the problem as I understood it and when 3 correctness tests didn’t pass, no matter how I tried to improve the solution, I googled and found yours. It passes 100% but it seems that the problem’s definition is contradictory.
I’ll try to explain what I mean:
1) the definition never mentions that the max value of the permutation elements should be equal or less than the array’s length (you do this check

2) It does say:
Assume that:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [1..1,000,000,000].
3) according to pp. 1 & 2 the solution should return 1 for the following arrays:
A [121,050]
A [121,052]
A [121,051]
and
A 
A 
Nevertheless, your solution returns 0 on them.
I would appreciate if you could point where in the problem’s definition is it clearly explained why this should work like that (and in contradiction to the explicit assumptions)?
Thanks!

• Sheng says:

• Sergio says:

Ok, thanks 🙂 What do you say about the question?

• Sheng says:

I do not understand your given example in (3). But for (1) you do miss one statement in the question: A permutation is a sequence containing each element from 1 to N once, and only once.

• Sergio says:

In regard to the statement, as N is mentioned in relation to the number of array’s elements (not their values), I understand it as that each element (“from 1 to N” meaning “from the first to the last element of the sequence”) is not repeated in the sequence. It doesn’t say that the element’s value shoud be from 1 to N. If it said so it would be an incorrect definition of permutation; when I read “A permutation is…” I assume that it is referring to the mathematical definition and the min value of permutation elmenents doesn’t have to start with 1.
As for the example, I suggest these arrays:
int[] array = {121050, 121052, 121051}
int[] array = {42, 41}
According to the assumtions this should return 1, as being permutations of the following sequences:
121050, 121051, 121052
41, 42
Even assuming that (in this problem) the permutation elements should have min value 1, your code will fail for the array int[] array = {1, 2 .. 100000, 100001}, though it should work according to:
Assume that:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [1..1,000,000,000].
because it will be longer than the assumed range though within the range of element values. (This contradiction between the max array length and max element value exists only if we assume that the min value of permutation elements should be 1.)
To resume, I see the following contradictions:
1. There is no a clear indication that the min value should always be 1
2. There is no any indication that the element max value should be limited by array’s length (except for the case that the min value should always be 1)
3. Even if we assume the min value being 1, how do we fit it with the assumption that the element max value may be up to 1,000,000,000 and the max array length is limited to 100,000
I hope I could explain myself.

• Sheng says:

1. 2. The formal def in math might be different. But here Codility does define these permutations, starting with 1 and ending with N, where N is the array length.
3. The assumption is for all input, which may contain invalid ones.
4. {1, 2 .. 100000, 100001} is not in our consideration. As the assumption, it will never appear in the test cases. A possible input would be {1, 2, 3, … 99999, 1000000000}, which follow the assumption and not a permutation.
This becomes a language debate. It is meaningless to carry any further discussion for this.

• Sergio says:

Ok, agree. Nevertheless, I believe that a clear, unambiguous definition of the problem not only would avoid this kind of discussions but also should be the necessary requirement when testing programming abilities.
Thank you for taking the time to answer my doubts.

• Sheng says:

Yes, I agree with you. But neither of us is the one, who make this challenge. We can only guess. And it is helpless.

10. Mathieu says:

Why not use set() ?

• Sheng says:

Set is awesome and perfect in this solution. However, in theory, the worst-case performance of set operations is O(N), not O(1).
In addtion, I forgot to use set at the first sight 🙂 Thanks!

• Priya says:

elegant solution!

11. calinutz says:

My first Pascal solution would be: if the array contains a permutation, then it contains all numbers from 1 to N. That would mean that the sum of all elements would be equal to 1+2+3+…+N. The array has indexes from 0 to N-1. So basically if an array has N=5 then the sum of all elements should be
1+2+3+4+5, and the sum of all indices would be 0+1+2+3+4. That means if we add N to the sum of indices we should obtain the sum of the contents of the array…
I do not know if you understand, but it seems logical to me.
So N=5
sum_of_indices = 0+1+2+3+4
sum_of_contents= a+a+a+a+a = 1+2+3+4+5 (in some other order)
so sum_of_indices+N should equal sum_of_contents
That is unless I missunderstood the problem.
Anyway my code in Pascal is:

However… the score is 80% and 60%… because:
antiSum1
total sum is correct, but it is not a permutation, N &lt= 10 0.001 s WRONG ANSWER
got 1 expected 0
and
antiSum2
total sum is correct, but it is not a permutation, N = ~100,000 0.096 s WRONG ANSWER
got 1 expected 0
and
extreme_values
all the same values, N = ~100,000 0.001 s WRONG ANSWER
got 1 expected 0
Does anybody have any idea why is this happening? And what does antiSum1 and antiSum2 mean?
I do not see any explanation for my code being wrong. Please enlighten me.
(also format my code for the “less than” sign)

• Sheng says:

Probably some elements are less than 1 or larger than N (the number of elements in A).

12. a131a says:

Ruby 100%

13. Santosh says:

• Sheng says:

Please take a look at the “Guideline for Comments” at the right column.

• Sheng says:

I do not know much about JS. But it is alright to get “Detected time complexity: O(N) or O(N * log(N)).”
O(N*logN) is very close to O(lN), since logN is typically very small. And it is hard for codility or any OJ system to distinguish O(N) and O(N*logN).

14. Antonio Correia says:

A c++11 solution

15. Roberto Gonzalez says:

This is my Java solution:

• Sheng says:

Thanks for sharing!!!
PS: I like your static final variables.

16. Will says:

Wasn’t sure if this was on here but here is a solution which is not only faster on large sets but checks for sum to bypass unneeded calculations on easy fails.

• Sheng says:

Your solution uses sorting, which is O(N*logN). It should be slower than the orginal O(N) solution.
PS: the old solution uses addition operation, which is useless. It is fixed now.

17. Paulo says:

18. Manish Agarwal says:

Hi, hers is my Java solution but it say 70% score

• Sheng says:

Consider [2, 2, 2].

19. sharon says:

hi Sheng,
i think the details of the tests are not insufficient.
cause, for ex, one of the tests are named “single element” , and there i got in one OK and on the other Wrong , and now i could i know in which exactly element it is failed?
thanks,
sharon

• Sheng says:

Hello! You could simply print out the testing data, like “print” int Python.

20. KEMBL says:

C# 100%

21. victor says:

Hi Sheng,
This question did not give me second parameter, so could I use max(A) to get the largest element of A, so that I can use  * (A+1) to create the count array.

• Sheng says:

There is no second parameter. And your solution is incorrect. Try [4, 5, 6, 4, 5, 6] .

22. Ferry says:

Hi Sheng,
Here is my solution. I got 100 but I still not sure this is good solution.

• Sheng says:

23. Gshekhar says:

C# Solution 100%

24. Vladimir Cezar says:

My 100% correct Swift Solution

• Sheng says:

25. Bogdan says:

Interestingly, the Codility test cases do not use 0 values in this test, as the following solution returns 100%-100%, regardless the fact that on the array [0, 1, 2, 3] it throws an IndexOutOfRangeException, as expected otherwise.

• Sheng says:

The problem says: “each element of array A is an integer within the range [1..1,000,000,000].” So we do not need to consider 0.

26. Pavlos Fragkiadoulakis says:

The Xor solution is perfect here and the best one. You should be fond of the Xor answer. The C code follows:

Note that the above code works only if s is declared as long. I saw the comments above, however, all test cases in codility are marked as perfect (100%).

• Sheng says:

Unfortunately, your solution is wrong. Try [3,4,7].

27. Davide says:

My Java solution (100%)

28. Gerald says:

this is my own code, please check it out:

• Sheng says:

Logically right. But its time complexity does not meet the requirement.

29. Baolin Liu says:

Any thoughts?

• Sheng says:

As far as I can see, it works well. (Thanks to Python, we do not have overflow issue for “total”.)

• Baolin Liu says:

thanks sheng

30. meceyurt says:

31. Zero Killa says:

32. Jorge says:

This is my solution:

33. Max says:

34. Mustafa Ates says:

Java %100 Solution

35. Sten says:

My Java solution, O(n)/O(1):

36. Nate says:

My solution (very similar to yours) got 100% but I am new to coding and not sure if either is better:

37. Nadine says:

Task Score:100%, Correctness:100%,Performance:100%. Solved in PHP

38. Vipul Gaur says:

Didn’t use counter, solved it using xor_sum

• Vipul Gaur says:

100% correctness and 100% performance

• Darren Ng says:

It wouldn’t work with a perm set that’s [3,5,2,4,1]. Try it. In fact, your code wouldn’t work with any perm set that’s randomised because your xor_sum is almost always guaranteed to not equal 0 even if it’s a perm set.

39. Roberson Faria says:

Python 100%

40. Jason says:

Python 100%

41. DimitrisBor says:

Javascript

42. Barbara K says:

Python 100%

43. Anand says:

Yet another Python solution using a set:

44. raul says:

My 100% solution using python:

45. Jay Bariya says:

Python code – 100%. Detected time complexity – O(N) or O(N*log(N)).