Solution to Perm-Check by codility

19 Jan

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:

The Java solution is:

65 thoughts on “Solution to Perm-Check by codility

  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.

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

  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.

  4. we can do the same question by using xor operation:

    and its working 100% correct

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

  5. PHP 100%

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

  7. Here is my solution in javascript.

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

  9. Why not use set() ?

  10. 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 &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)

  11. Ruby 100%

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

  12. A c++11 solution

  13. This is my Java solution:

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

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

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

  17. C# 100%

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

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

  19. C# Solution 100%

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

  21. 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%).

  22. My Java solution (100%)

  23. this is my own code, please check it out:

Leave a Reply

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