Test results - Codility

Your browser is not supported. Please, update your browser or switch to a different one. Learn more about which browsers are supported.

Tasks Details

easy

1. PermCheck

Check whether array A is a permutation.

Task Score

100%

Correctness

100%

Performance

100%

Task description

A non-empty array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

A[0] = 4 A[1] = 1 A[2] = 3 A[3] = 2

is a permutation, but array A such that:

A[0] = 4 A[1] = 1 A[2] = 3

is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function:

object Solution { def solution(a: Array[Int]): Int }

that, given an array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:

A[0] = 4 A[1] = 1 A[2] = 3 A[3] = 2

the function should return 1.

Given array A such that:

A[0] = 4 A[1] = 1 A[2] = 3

the function should return 0.

Write an efficient algorithm for the following assumptions:

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

Solution

Programming language used Scala

Time spent on task 18 minutes

Notes

not defined yet

Task timeline

‌

Code: 05:44:51 UTC, scala, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12


import java.util.BitSet

object Solution {
    def solution(A: Array[Int]): Int = {
        val set = new BitSet(A.size + 1)
        val good = A.foldLeft(false)((l, r) => true)
        
        if (good) 1
        else 0
    }
}

Analysis

expand all Example tests

▶

example1
the first example test

✔

2.299 s

▶

example2
the second example test

✘

WRONG ANSWER
got 1 expected 0

2.329 s

WRONG ANSWER, got 1 expected 0

Code: 05:45:11 UTC, scala, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14


import java.util.BitSet

object Solution {
    def solution(A: Array[Int]): Int = {
        val set = new BitSet(A.size + 1)
        val good = A.foldLeft(false)((l, r) => 
            true
        )
        
        if (good) 1
        else 0
    }
}

Analysis

expand all Example tests

▶

example1
the first example test

✔

2.293 s

▶

example2
the second example test

✘

WRONG ANSWER
got 1 expected 0

2.297 s

WRONG ANSWER, got 1 expected 0

Code: 05:54:36 UTC, scala, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31


import java.util.BitSet

object Solution {
    def solution(A: Array[Int]): Int = {
        val bitz = new BitSet(A.size + 1)
        
        val good = A.foldLeft(true)((current, i) => 
            if (current) {
                (i, bitz.get(i)) match {
                    case (x, _) if x > A.size + 1 => 
                        false
                        
                    case (0, _) => 
                        false
                        
                    case (_, true) => 
                        false
                        
                    case _ =>
                        bitz.set(i)
                        true
                }
                
            } else false
        )
        
        if (good) 1
        else 0
    }
}

Analysis

expand all Example tests

▶

example1
the first example test

✔

2.368 s

▶

example2
the second example test

✘

WRONG ANSWER
got 1 expected 0

2.356 s

WRONG ANSWER, got 1 expected 0

Code: 05:55:39 UTC, scala, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31


import java.util.BitSet

object Solution {
    def solution(A: Array[Int]): Int = {
        val bitz = new BitSet(A.size + 1)
        
        val good = A.foldLeft(true)((current, i) => 
            if (current) {
                (i, bitz.get(i)) match {
                    case (x, _) if x > A.size => 
                        false
                        
                    case (0, _) => 
                        false
                        
                    case (_, true) => 
                        false
                        
                    case _ =>
                        bitz.set(i)
                        true
                }
                
            } else false
        )
        
        if (good) 1
        else 0
    }
}

Analysis

expand all Example tests

▶

example1
the first example test

✔

2.080 s

▶

example2
the second example test

✔

2.347 s

Code: 05:56:04 UTC, scala, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31


import java.util.BitSet

object Solution {
    def solution(A: Array[Int]): Int = {
        val bitz = new BitSet(A.size + 1)
        
        val good = A.foldLeft(true)((current, i) => 
            if (current) {
                (i, bitz.get(i)) match {
                    case (x, _) if x > A.size => 
                        false
                        
                    case (0, _) => 
                        false
                        
                    case (_, true) => 
                        false
                        
                    case _ =>
                        bitz.set(i)
                        true
                }
                
            } else false
        )
        
        if (good && A.size > 0) 1
        else 0
    }
}

Analysis

expand all Example tests

▶

example1
the first example test

✔

2.388 s

▶

example2
the second example test

✔

2.394 s

Code: 05:56:47 UTC, scala, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31


import java.util.BitSet

object Solution {
    def solution(A: Array[Int]): Int = {
        val bitz = new BitSet(A.size + 1)
        
        val good = A.foldLeft(true)((current, i) => 
            if (current) {
                (i, bitz.get(i)) match {
                    case (x, _) if x > A.size => 
                        false
                        
                    case (0, _) => 
                        false
                        
                    case (_, true) => 
                        false
                        
                    case _ =>
                        bitz.set(i)
                        true
                }
                
            } else false
        )
        
        if (good && A.size > 0 && N > 1 && N <= 100000) 1
        else 0
    }
}

Analysis

Compile error

Solution.scala:28: error: not found: value N
        if (good && A.size > 0 && N > 1 && N <= 100000) 1
                                  ^
Solution.scala:28: error: not found: value N
        if (good && A.size > 0 && N > 1 && N <= 100000) 1
                                           ^
two errors found

Code: 05:58:00 UTC, scala, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34


import java.util.BitSet

object Solution {
    def solution(A: Array[Int]): Int = {
        val bitz = new BitSet(A.size + 1)
        
        val good = A.foldLeft(true)((current, i) => 
            if (current) {
                (i, bitz.get(i)) match {
                    case (x, _) if x > A.size => 
                        false
                        
                    case (x, _) if x < 1 || x > 1000000000 => 
                        false
                        
                    case (0, _) => 
                        false
                        
                    case (_, true) => 
                        false
                        
                    case _ =>
                        bitz.set(i)
                        true
                }
                
            } else false
        )
        
        if (good && A.size > 0) 1
        else 0
    }
}

Analysis

expand all Example tests

▶

example1
the first example test

✔

2.375 s

▶

example2
the second example test

✔

2.382 s

Code: 05:58:21 UTC, scala, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34


import java.util.BitSet

object Solution {
    def solution(A: Array[Int]): Int = {
        val bitz = new BitSet(A.size + 1)
        
        val good = A.foldLeft(true)((current, i) => 
            if (current) {
                (i, bitz.get(i)) match {
                    case (x, _) if x > A.size => 
                        false
                        
                    case (x, _) if x < 1 || x > 1000000000 => 
                        false
                        
                    case (0, _) => 
                        false
                        
                    case (_, true) => 
                        false
                        
                    case _ =>
                        bitz.set(i)
                        true
                }
                
            } else false
        )
        
        if (good && A.size > 0 && A.size <= 100000) 1
        else 0
    }
}

Analysis

expand all Example tests

▶

example1
the first example test

✔

2.362 s

▶

example2
the second example test

✔

2.354 s

Code: 05:58:42 UTC, scala, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34


import java.util.BitSet

object Solution {
    def solution(A: Array[Int]): Int = {
        val bitz = new BitSet(A.size + 1)
        
        val good = A.foldLeft(true)((current, i) => 
            if (current) {
                (i, bitz.get(i)) match {
                    case (x, _) if x > A.size => 
                        false
                        
                    case (x, _) if x < 1 || x > 1000000000 => 
                        false
                        
                    case (0, _) => 
                        false
                        
                    case (_, true) => 
                        false
                        
                    case _ =>
                        bitz.set(i)
                        true
                }
                
            } else false
        )
        
        if (good && A.size > 0 && A.size <= 100000) 1
        else 0
    }
}

Analysis

expand all Example tests

▶

example1
the first example test

✔

2.337 s

▶

example2
the second example test

✔

2.191 s

Code: 05:59:00 UTC, scala, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34


import java.util.BitSet

object Solution {
    def solution(A: Array[Int]): Int = {
        val bitz = new BitSet(A.size + 1)
        
        val good = A.foldLeft(true)((current, i) => 
            if (current) {
                (i, bitz.get(i)) match {
                    case (x, _) if x > A.size => 
                        false
                        
                    case (x, _) if x < 1 || x > 1000000000 => 
                        false
                        
                    case (0, _) => 
                        false
                        
                    case (_, true) => 
                        false
                        
                    case _ =>
                        bitz.set(i)
                        true
                }
                
            } else false
        )
        
        if (good && A.size > 0 && A.size <= 100000) 1
        else 0
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N) or O(N * log(N))

expand all Example tests

▶

example1
the first example test

✔

2.339 s

▶

example2
the second example test

✔

2.242 s

expand all Correctness tests

▶

extreme_min_max
single element with minimal/maximal value

✔

2.083 s

2.366 s

▶

single
single element

✔

2.356 s

2.355 s

▶

double
two elements

✔

2.371 s

2.361 s

2.350 s

2.353 s

▶

antiSum1
total sum is correct, but it is not a permutation, N <= 10

✔

2.358 s

2.350 s

2.361 s

▶

small_permutation
permutation + one element occurs twice, N = ~100

✔

2.342 s

2.369 s

expand all Performance tests

▶

medium_permutation
permutation + few elements occur twice, N = ~10,000

✔

2.700 s

2.755 s

▶

antiSum2
total sum is correct, but it is not a permutation, N = ~100,000

✔

2.900 s

2.925 s

▶

large_permutation
permutation + one element occurs three times, N = ~100,000

✔

2.933 s

2.875 s

▶

large_range
sequence 1, 2, ..., N, N = ~100,000

✔

2.765 s

2.878 s

▶

extreme_values
all the same values, N = ~100,000

✔

2.353 s

2.698 s

2.345 s