Codility ‘PermCheck’ Solution

Short Problem Definition:

Check whether array N is a permutation.

Link

PermCheck

Complexity:

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

expected worst-case space complexity is O(N)

Execution:

Mark elements as seen in a boolean array. Elements seen twice or out of bounds of the size indicate that the list is no permutation. The check if the boolean array only contains true elements is not required. This solution only works with permutations starting from 1.

Solution:
def solution(A):
    seen = [False] * len(A)

    for value in A:
        if 0 <= value > len(A):
            return 0
        if seen[value-1] == True:
            return 0
        seen[value-1] = True

    return 1

int solution(vector<int> &A) {
    // the use of a auto_ptr would be better, but it does not work with arrays
    // use of boost::scoped_array seems like an overkill
    bool * seen = new bool[A.size()];
    
    for (unsigned int i=0; i< A.size(); i++){
        seen[i] = false;
    }    
    
    for (unsigned int i=0; i< A.size(); i++){
        if (!(0 < A[i] && A[i] <=A.size() && seen[A[i]-1] == false)){
            delete[] seen;
            return 0;
        } else {
            seen[A[i]-1] = true;
        }
    }
    
    delete[] seen;
    return 1;
}

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

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Sasha Shipka

    def solution(A):
    # write your code in Python 2.7
    return 1 if (set(A) == set(range(1, len(A)+1))) else 0

    • I love your use of the Python language 🙂

      • Sasha Shipka

        Just a ‘brain damage’ I have by using Haskell for fun and Common Lisp in every day job. 🙂 Using them for these problems would be fun too.

        • I must be damaged by daily ANSI C ;). Anyways, I always try to make the code posted on the blog to be translatable into other languages without too much effort 😉

          • Sasha Shipka

            I completely understand and support your way here, the universal approach to solve tests in any language.
            I tried to demonstrate some python simplicity. In different languages we think and solve problems differently, depending on what language has to offer.

  • Siavash Goudarzi

    PHP:

    function solution($A) {
    if (!($c = count($A)) || $c !== count(array_unique($A)))
    return 0;
    return $c === max($A) ? 1 : 0;
    }