Question: http://codility.com/demo/take-sample-test/perm_check
Question Name: PermCheck
This question is a simple variant of the counting question. The Python solution is:
1 2 3 4 5 6 7 8 9 10 11 12 | def solution(A): counter = [0]*len(A) limit = len(A) for element in A: if not 1 <= element <= limit: return 0 else: if counter[element-1] != 0: return 0 else: counter[element-1] = 1 return 1 |
The Java solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public static int solution(int[] A) { int[] counter = new int [A.length]; for(int i= 0; i< A.length; i++){ if (A[i] < 1 || A[i] > A.length) { // Out of range return 0; } else if(counter[A[i]-1] == 1) { // met before return 0; } else { // first time meet counter[A[i]-1] = 1; } } return 1; } } |
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?
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.
don’t know why it is missing some part of the code in posting a comment
Please post your code inside a <pre> … </pre> block.
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.
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.
This also only works for positive numbers right?
No. It works for all cases.
the code doesnt work properly for A = [1,2] should return 1 not 0
It does return 1, which is correct.
it is returning only 0’s for all arrays…
How about [1, 2, 3].
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[0] = 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.
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.
we can do the same question by using xor operation:
and its working 100% correct
Better than mine! Great solution!Sorry, even thought it passed all test, it might be wrong. Try [3, 5, 6]
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?
Awesome explanation! Thank you for the high-quanlity comment!
I will add a plugin for live comment preview.
Question Says the array contains the elements 1 to N.
You have taken the array elements starting from 3.
Question says the array starts with 1. You have taken the first element as 3.
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.
PHP 100%
Thanks for sharing your solution!
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.
Yes, you can use boolean[]. Bitmap works also.
PS: thanks for your comment!
Here is my solution in javascript.
Thanks for sharing your solution!
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[0] [121,050]
A[1] [121,052]
A[2] [121,051]
and
A[0] [42]
A[1] [41]
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!
I corrected your code.
Ok, thanks 🙂 What do you say about the question?
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.
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.
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.
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.
Yes, I agree with you. But neither of us is the one, who make this challenge. We can only guess. And it is helpless.
Why not use set() ?
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!
elegant solution!
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[0]+a[1]+a[2]+a[3]+a[4] = 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 <= 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)
Probably some elements are less than 1 or larger than N (the number of elements in A).
Ruby 100%
C# solution (apparantly 100%) .. any comments please?
Please take a look at the “Guideline for Comments” at the right column.
I have a problem with JS. I tried many times but always get:
Detected time complexity: O(N) or O(N * log(N)). Is this acceptable?
https://codility.com/demo/results/demoCKYXUH-VHW/
https://codility.com/demo/results/demoZMBPVA-4FB/
https://codility.com/demo/results/demo6U5C3Z-8A3/
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).
A c++11 solution
This is my Java solution:
Thanks for sharing!!!
PS: I like your static final variables.
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.
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.
Hi, hers is my Java solution but it say 70% score
Consider [2, 2, 2].
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
Hello! You could simply print out the testing data, like “print” int Python.
C# 100%
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 [0] * (A+1) to create the count array.
There is no second parameter. And your solution is incorrect. Try [4, 5, 6, 4, 5, 6] .
Hi Sheng,
Here is my solution. I got 100 but I still not sure this is good solution.
Please read “Guideline for Comments” before posting your code. I cannot see your complete code. But as far as I see, your solution is good.
C# Solution 100%
My 100% correct Swift Solution
Please read the “Guideline for Comments” in the right column for posting codes. Thanks!
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.
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.
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%).
Unfortunately, your solution is wrong. Try [3,4,7].
My Java solution (100%)
this is my own code, please check it out:
Logically right. But its time complexity does not meet the requirement.
Any thoughts?
As far as I can see, it works well. (Thanks to Python, we do not have overflow issue for “total”.)
thanks sheng
This is my solution:
Java %100 Solution
My Java solution, O(n)/O(1):
My solution (very similar to yours) got 100% but I am new to coding and not sure if either is better:
Task Score:100%, Correctness:100%,Performance:100%. Solved in PHP
Didn’t use counter, solved it using xor_sum
100% correctness and 100% performance
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.
Python 100%
Python 100%
Javascript
Python 100%
Yet another Python solution using a set:
My 100% solution using python:
Python code – 100%. Detected time complexity – O(N) or O(N*log(N)).