Codility PermCheck why my solution is not working

Question

I'm trying to solve Codility lessons for coding practice and PermCheck is one of them.

[Edit] Problem Description:

A non-empty zero-indexed 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: class Solution { public int solution(int[] A); } that, given a zero-indexed 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. 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].

My solution at the moment is:

class Solution {
    public int solution(int[] A) {

        final int N = A.length;
        long sum = N * (N+1)/2;

        for(int i=0; i<A.length; i++) {
            sum -= A[i];
        }

        return sum == 0 ? 1 : 0;
    }
}

and the results are not what I am expecting. I know that many solutions are out there but I want to know what's the problem with my solution. What corner cases I am missing. The results page does not show the input list on which the above solution is failing.

Dyson

But what I understand from the problem description is that it's a series of positive int with no duplicates. So if there will be any duplicate sum will not be 0. Am I right ? – Dyson

Answer 1

The reason this isn't working is that a permutation (as explained) is not the only way to arrive at a particular sum, as your solution assumes. For example:

[0, 1, 2, 3] // Sum == 6
[0, 2, 2, 2] // Sum == 6

According to the problem description as written, I don't believe it implies the given data has no duplicates.

Atavism

I believe this is correct--the description says a permutation has no duplicates, but gives no assurance against duplicates in the input data. – Ritchie

Answer 2

If N is 100,000, then the N * (N + 1) / 2 expression causes integer overflow(eventhough sum is a long, N is an int). Not sure if there are other bugs.

Treble

yes, that's possible. But that's not what happening at the moment. But nonetheless good point to raise. +1 for that – Dyson

Answer 3

Code: 08:25:58 UTC, c, final, score: 100.00

   int solution(int A[], int N) {
    // write your code in C99

    int T[N];
//when the compiler sees N variable declaration it cannot know how many         
//elements there are in the array.
//must manually initialize that array.
    memset( T, 0, N*sizeof(int) ); 
    for (int i=0;i<N;i++)
    {
    if (A[i]>N)
        {
        return 0;
        }
    T[A[i]-1]++;
    }
    int sum=0;
   for (int i=0;i<N;i++)
    {
    sum =sum+T[A[i]-1];
    }
    return (sum==N)?1:0;
}

Hereupon

Answer 4

You can just add them to a set and check the length at the end. If any of the values in the list are greater than the list size you can early out, as it's never going to be a valid perm.

https://app.codility.com/demo/results/training47WAU6-G8F/

import java.util.*;

class Solution {
    public int solution(int[] A)
    {
        Set<Integer> all = new HashSet<Integer>();
        
        for( int v : A )
        {
            if( v > A.length ) return 0;
            all.add(v);
        }
        
        return all.size() == A.length ? 1:0;
    }
}

Bono

Answer 5

My solution In python.

 def solution(A):
    # write your code in Python 3.6
    N = len(A)
    sum1 =sum(range(1, N+1))
    sum2 = sum(A)
    if len(set(A)) != len(A):
        return 0
    if (sum1 - sum2) != 0:
        return 0
    return 1 

Illiberal

Answer 6

XOR solution in Python with complexity of O(N), this works on the idea that X ^ X = 0 and 0 ^ X = x

def solution(A):
    chk = 0
    l = len(A)

    for i,x in enumerate(A):
        if x < 1 or x > l:
            return 0
        else:
            chk = chk ^ i+1 ^ x
    if chk != 0:
        return 0
    else:
        return 1 

Quadrangular

Answer 7

A javascript solution with 100% passing result:

function solution(A) {
    A.sort(function(a,b){
       return a - b; 
    });
    var count = 0;
    for(i = 0; i < A.length; i++){
        if(A[i] === i+1){
            count++;
        } else {
            break;
        }
     } 
    if(count === A.length){
     return 1;   
    }
    else {
     return 0;   
    } 
}

Ainslie

Why do you need the counter? you can just return if the condition fails – Justicz

Great solution. Little refactored version could be written like this function solution(arr){ arr.sort(function(a,b){ return a - b; }) for(i = 0; i < arr.length; i++){ if(!(arr[i] === i+1)) return 0 } return 1 } – Metropolis

Answer 8

If duplicate exists - return 0 I have implemented with 100% pass

https://codility.com/demo/results/trainingWX2E92-ASF/

public static int permCheck(int A[]){

    Set<Integer> bucket = new HashSet<Integer>();
    int max = 0;
    int sum=0;
    for(int counter=0; counter<A.length; counter++){
        if(max<A[counter]) max=A[counter];
        if(bucket.add(A[counter])){
            sum=sum+A[counter];
        }
        else{
            return 0;
        }
    }
    System.out.println(max+"->"+sum);
    int expectedSum = (max*(max+1))/2;
    if(expectedSum==sum)return 1;

    return 0;
}

Dithyrambic

Answer 9

Here is the solution in java 100% in codility.

import java.util.TreeSet;

class Solution {

 public int solution(int[] A) {
    TreeSet<Integer> hset = new TreeSet<Integer>();
    int total_value=0;
    long total_indexes = A.length * (A.length+1)/2;
    for (int i = 0; i < A.length; i++) {
        hset.add(A[i]);
        total_value+=A[i];
    }
    if (hset.size() == hset.last() && total_indexes==total_value) {
        return 1;
    }
    return 0;
 }
}

Grateful

Answer 10

I believe all the solutions that depend on sorting are wrong! Because the required time complexity is O(N); and sort cannot be O(N).

* oh and my python solution is

def solution(A):
    holes = [0]*(1+len(A))    # holes[0] isn't used
    for i in A:
        # if i is larger than N then it's not a permutation
        # if i appeared before in A, then the hole[i] should be 1, in such case it's not a permutation as well
        if i>len(A) or holes[i]==1:
            return 0
        holes[i] = 1
    return 1

Chiao

Answer 11

C++ score: 100.

The idea is we make a new array B has N+1 elements and all false, then set B[A[i]] = true. Iterate on B if we found any B[i] is false then return 0, otherwise 1.

Complexity is O(2N) ~= O(N).

#include <vector>

using namespace std;

int solution(vector<int> &A) {
    int n = A.size();

    vector<bool> v;
    v.resize(n + 1);

    for (int i = 0; i < n; i++) {
        int element = A[i];
        if (element > n) {
            return 0;
        }
        if (v[element]) {
            return 0;
        }
        v[element] = true;
    }
    for (int i = 1; i < v.size(); i++) {
        if (!v[i]) {
            return 0;
        }
    }
    return 1;
}

Philender

Answer 12

I understand that since this lesson require O(n), so the solution should without sorting. the keyword about permutation is sequence and 1 to N only once. so the solution should check duplicate and all elements in sequence.

public static int solution(int[] A)
    {
        if (A.Length == 1) return 1;

        var max = 0;

        var dic = new Dictionary<int, int>();

        //find duplicate
        for (var i = 0; i < A.Length; i++)
        {
            if (A[i] > max) max = A[i];

            if (!dic.ContainsKey(A[i]))
            {
                dic.Add(A[i], 1);
                continue;
            }

            dic[A[i]]++;
            if (dic[A[i]] > 1) return 0;
        }

        //check in sequence
        for (var i = 1; i <= max; i++)
        {
            if (!dic.ContainsKey(i))
            {
                return 0;
            }
        }

        return 1;
    }

However, this code failed extreme_min_max and single tests, don't know why as the code check if array A length is 1, just return 1.

Knott

Answer 13

Solution in PHP with 100% on the three fields:

function solution($A) {

    $size = count($A); // SIZE OF ARRAY
    $sum = array_sum($A); // SUM OF ALL ELEMENTS

    $B = array(); // WE CHECK FOR ARRAYS WITH REPEATED VALUES 
    foreach($A as $key=>$val) {    
        $B[$val] = true; 
    } 
    $B= array_keys($res2); // A FOREACH AND ARRAY_KEYS IS 30x TIMES FASTER THAN ARRAY_UNIQUE 

    if($size != count($res2)) return 0; //IF THE SIZE IS NOT THE SAME THERE ARE REPEATED VALUES

    $total = ( $size * ( $size + 1) ) / 2; // WE CHECK FOR THE SUM OF ALL THE INTEGERS BETWEEN OUR RANGE
    return $sum == $total ? 1 : 0; // IF SUM OF ARRAY AND TOTAL IS EQUAL IT IS A PERMUTATION IF NOT THERE ARE SOME NUMBERS MISSING BUT NONE ARE REPEATED
}

Satisfied

Answer 14

This is my solution

function solution(A) {
    const t = A.reduce((acc, cur, index) => acc ^ cur ^ (index + 1), 0)
    return A.reduce((acc, cur, index) => acc ^ cur ^ (index + 1), 0) === 0 ? 1 : 0
}

^ is awesome.

Deforest

Answer 15

Here's my solution with 100% score. No extra space is needed and also, it gives O(n) time complexity. It works by marking the current element visited by setting the element at its corresponding index to negative. For e.g. 1 could be anywhere in the array but if the element at 0th index is negative, that means 1 is visited.

function solution(A) {
    for(let i=0 ;i< A.length;  i++){
        const elementIndex = Math.abs(A[i]) - 1;
        if(elementIndex < A.length){
           A[elementIndex] = -A[elementIndex];
        }
    }

    for(let i=0 ;i< A.length;  i++){
        if(A[i] > 0) {
            return 0;
        }
    }

    return 1;
}

Ombre

Answer 16

Here's a simple one in Python:

def solution(A):
    # write your code in Python 3.6
    N = len(A)
    occurance = {}
    A.sort()
    if A[-1] == N:
        for item in A:
            if item <= 0:
                return 0
            elif item not in occurance:
                occurance[item] = True
            else:
                return 0
        return 1
    else:
        return 0

Digiovanni

Answer 17

js solution (100/100 - O(N))

function solution(A) {
  for (let i = 0; i < A.length; i++)
    if (A[i] > A.length) return 0;
  return new Set(A).size === A.length ? 1 : 0;
};

Meader

Best minimal JavaScript code – Doug

Answer 18

def solution(A):
    n = len(A)
    s = sum(set(A))
    sum_seq = n * (n + 1) / 2
    if s == sum_seq:
        return 1
    else:
        return 0

Westphalia

Answer 19

Another approach using List:

public int solution(int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
          List<double> sum = A.ToList().Select(x => (double)x).ToList();
            double maxElem = A.ToList().Max();
            double res = (maxElem * (maxElem + 1)) / 2;
            if (sum.Sum() == res && sum.Distinct().Count() == maxElem)
            {
                return 1;
            }
            else
            {
                return 0;
            }
    }

Doradorado

Answer 20

Here it is my solution in java:

/**
 * https://codility.com/demo/results/training4YUHYS-HDW/ 100%
 * 
 * Facts:
 * 1) A permutation is a sequence containing each element from 1 to N once, and only once.
 * 2) A non-empty zero-indexed array A consisting of N integers is given
 * 3) N is an integer within the range [1..100,000];
 * 4) each element of array A is an integer within the range [1..1,000,000,000].
 * 
 * Invariant: the sequence is in the range A[0] to A[N-1]
 * 
 * @param A
 * @return
 */
public static int solution(int[] A) {
    int result=1;
    int[] count = new int[A.length+1];
    for(int i=0; i<A.length; i++) {
        if(A[i]>A.length) return 0;
        if(count[A[i]]>0) return 0;
        count[A[i]]++;
    }
    for(int i=1; i<count.length; i++) {
        if(count[i]==0) {
            result =0;
            break;
        }
    }
    return result;
}

The time complexity is O(2n) wich is equal to O(n). https://codility.com/demo/results/training4YUHYS-HDW/

Redcoat

Answer 21

A simple and small solution would be:

public int solution(int[] A) {

        Arrays.sort(A);

        for (int i = 0; i < A.length; ++i) {
            if (A[i] != i + 1) {
                return 0;
            }
        }

        return 1;
}

Nonetheless, I think worst time complexity would be O(nlgn) because of the sorting.

Codility gave me 100 points and calculated time complexity as O(n)...

Fattal

wouldn't this fail for something like [2, 2, 3]? you're not checking if A[0] is 1 – Justicz

Answer 22

I have posted this solution right now, and it gave 100%. Maybe this helps to get any ideas...

    /**
     * Storage complexity O(N/64). That does mean that for 1000 elements array will be reserved
     *  only 16 additional long values.
     * Time complexity the same - O(N)
     * @author Egor
     *
     */
    public class SolutionBitFlags {

        private static final int ARRAY_SIZE_LOWER = 1;
        private static final int ARRAY_SIZE_UPPER = 1000000;
        private static final int NUMBER_LOWER = 1;
        private static final int NUMBER_UPPER = 1000000000;

        public static class Set {

            final long[] buckets;

            public Set(int size) {
                this.buckets = new long[(size % 64 == 0 ? (size/64) : (size/64) + 1)];
            }

            /**
             * number should be greater than zero
             * @param number
             */
            public void put(int number) {
                buckets[getBucketindex(number)] |= getFlag(number); 
            }

            public boolean contains(int number) {
                long flag = getFlag(number);
                // check if flag is stored
                return (buckets[getBucketindex(number)] & flag) == flag;
            }

            private int getBucketindex(int number) {
                if (number <= 64) {
                    return 0;
                } else if (number <= 128) {
                    return 1;
                } else if (number <= 192) {
                    return 2;
                } else if (number <= 256) {
                    return 3;
                } else if (number <= 320) {
                    return 4;
                } else if (number <= 384) {
                    return 5;
                } else 
                    return (number % 64 == 0 ? (number/64) : (number/64) + 1) - 1;
            }

            private long getFlag(int number) {
                if (number <= 64) {
                    return 1L << number;
                } else
                    return 1L << (number % 64);
            }
        }

        public static int solution(final int[] A) {
            if (A.length < ARRAY_SIZE_LOWER || A.length > ARRAY_SIZE_UPPER) {
                throw new RuntimeException("Array size out of bounds");
            }
            switch (A.length) {
            case 1:
                return (A[0] == 1 ? 1 : 0);
            case 2:
                return ((A[0] == 1 && A[1] == 2) || (A[0] == 2 && A[1] == 1) ? 1 : 0);
            default:
                {
                    // we have to check 2 conditions:
                    // - number is not out of range [1..N], where N - array size
                    // - number is unique
                    // if either of them fails - array is not permutation
                    int ai;
                    Set set = new Set(A.length);
                    for (int i = 0; i < A.length; i++) {
                        if ((ai = A[i]) < NUMBER_LOWER || ai > NUMBER_UPPER) {
                             throw new RuntimeException("Number out of bounds");
                        }
                        // check boundaries
                        if (ai > A.length) {
                            return 0;
                        } else {
                             // check if already present in set (if present - return 0)
                            if (set.contains(ai)) {
                                return 0;
                            } else {
                                // put to set (if not in set )
                                set.put(ai);
                            }
                        }
                    }
                }
                break;
            }
            return 1;
        }
    }

Senskell

Answer 23

20% performance score..

function solution(a){
    a = a.sort();
    for(var i=0; i < a.length; i ++){
        if(a[i] != i + 1){
            return 0;
        } 
    }

return 1;

}

100%

function solution(a){
    a = a.sort((a,b) => a - b);
    for(var i=0; i < a.length; i ++){
        if(a[i] != i + 1){
            return 0;
        } 
    }

    return 1;
}

Twospot

Answer 24

Codility is a bit stupid in this quiz: I have 100% correctness and 100% performance with this solution

using System;

class Solution
{
    public int solution(int[] A)
    {
        Array.Sort(A);

        for (int i = 0; i < A.Length; i++)
        { 
            if (i+1 != A[i])
            {
                return 0;
            }
        }
        return 1;
    }
}

but it should not pass performance test - it's O(n*logn) because of sorting, so it's worse than O(n).

Septimal

Answer 25

Simple solution 100%

public static int solution(final int[] A) {

Set<Integer> set = new HashSet<Integer>();

for (int i : A) {
  set.add(i);
}

boolean numberNotFound = false;
for (int i = 1; i <= A.length; i++) {

//If set does not contain the number, that's the point to stop
//checking and return as per the boolean value set

  if (!set.contains(i)) {
    numberNotFound = true;
    break;
  }

}

return numberNotFound ? 0 : 1;
}

Amidst

Answer 26

I think as it is count elements chapter the desired solution should use element counting and then checking if there is each element exactly one time in the buckets array. My Swift solution is like this. But not checked on Codility:

public func PermCheck(_ A : inout [Int]) -> Int
{
    var B = [Int](repeating: 0, count: max(A.max()!, A.count)+1)

    for a in A {
        B[a] += 1
    }
    var sum = 0

    for i in 1...A.count {
        sum += B[i]
    }

    print(B)

    return A.count == sum ? 1 : 0
}
A = [4,1,3,2]
print("PermCheck: ", PermCheck(&A))

Billfold

Answer 27

In Swift 4, 100%:

public func solution(_ A : inout [Int]) -> Int {
    if A.isEmpty {
        return 0
    }

    if A.count == 1 {
        return A[0] == 1 ? 1 : 0
    }

    for (index, elem) in A.sorted().enumerated() {
        if index + 1 != elem {
            return 0
        }
    }

    return 1
}

Snore

Answer 28

My JavaScript solution got 100 across the board. Basically, I run through the array once and make each value an index in a new array with a value set to true (or wtv, as long as it is truthy). While doing so, I check to see if any value already has been entered into the new array. Then, I loop through the array and immediately return 0 if any item is falsy. Close enough to O(2n), I suppose.

const permCheck = (A) => {
    orderedArr = [];
    for (let i = 0; i < A.length; i++) {
        if (orderedArr[A[i]]) { return 0; } // duplicate - we out
        orderedArr[A[i]] = true;
    }
    for (let i = 1; i < orderedArr.length; i++) {
        if (!orderedArr[i]) {
            return 0;
        }
    }
    return 1;
}

Chrisoula

Answer 29

The functional, Scala solution which also got 100%. Hope this will help someone.

def solution(a: Array[Int]): Int = {
  val unique = a.toSet
  def takeTillEndOrMissingElement = (1 to a.length).takeWhile(unique.contains)
  if (unique.size == a.length && takeTillEndOrMissingElement.size == a.length) 1 else 0
}

Hatchett

Answer 30

Pure Java gave me 100%:

public int solution(int[] A) {
    int check[] = new int[A.length];
    int max = 0;
    int total = 0;
    for (int i = 0; i < A.length; i++) {
        total += A[i];
        max += i + 1;
        if (A[i] > A.length || check[A[i]-1] > 0)
            return 0;
        else
            check[A[i]-1] = A[i];
    }
    return max == total ? 1 : 0;
}

Georgeannageorgeanne

Answer 31

A two - liner 100% solution in C#

public int solution(int[] A) {
    // write your code in C# 6.0 with .NET 4.5 (Mono)
    var A2 = Enumerable.Range(1, A.Length);
        return A2.Except(A).Count() == 0 ? 1 : 0;
}

Thessa

Answer 32

Solution in Python:

def solution(A):
    # write your code in Python 3.6
    if max(A)> len(A) or len(set(A))<len(A): 
        return 0
    else: 
        return 1

Ophicleide

Hi, this doesn't solve the question from the user. He clearly didn't ask for a solution but for an explanation. – Borreri

Answer 33

My readable solution based on simple math (sets difference) to check the permutation:

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int[] A) {
        return isPermutation(A) ? 1 : 0;
    }

    private boolean isPermutation(int[] A) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        for (int i = 0; i < A.length; i++) {
            set1.add(A[i]);
            set2.add(i + 1);
        }
        set2.removeAll(set1);
        return set2.isEmpty();
    }
}

total score 100% and the detected time complexity: O(N) or O(N * log(N))

Haggerty

Answer 34

in Python:

def solution(A):
    new_list = [i for i in range(min(A), max(A), 1)]
    if len(set(new_list) - set(A)) > 0: return 0
    else: return 1
    
    pass

Pluralize

Answer 35

public func solution(_ A : inout [Int]) -> Int {
// write your code in Swift 4.2.1 (Linux)
 if A.count == 0 {
    return 0
}

var arr = A.sorted(by : {$0 < $1})
if arr[0] != 1{
    return 0
}

for i in 0..<arr.count - 1{
    
    if arr[i] + 1 != arr[i + 1]{
        return 0
    }
}

return 1
} 

Hortenciahortensa

Answer 36

My answer using java hit 100% more simple and easy to understand hope this helps:

public static int solution(int [] A){
       
  Arrays.sort( A );
  int index = 1;

  for ( int i = 0 ; i < A.length ; i++ )
  { 
    if ( A [ i ] ! = index)
    {
      return 0;
    }
    index++;
  }
  return 1;
}

Incoming

While this code may answer the question, providing additional context regarding how and/or why it solves the problem would improve the answer's long-term value. – Hintze

Answer 37

C# 100% solution

using System;

class Solution {
    public int solution(int[] A) {
        // write your code in C# 6.0 with .NET 4.5 (Mono)
        bool[] boolArray = new bool[A.Length];

        foreach(var v in A)
        {
            try
            {
                boolArray[v-1] = true;
            }
            catch
            {
                return 0;
            }
        }
           
        foreach (var v in boolArray)
        {
            if(v==false)
                return 0;
        } 

        return 1;
    }
}

Grandpa

Please edit your answer to explain what was wrong with the code in the question. – Sain

Answer 38

java 100:

    Arrays.sort(A);
    if (A[0] != 1 || A[A.length - 1] != A.length)
        return 0;

    HashSet<Integer> set = new HashSet<Integer>();
    for (int i = 0 ; i < A.length; i++){
        set.add(A[i]);
    }

    if (set.size() != A.length)
        return 0;

    return 1;

Judsen

Answer 39

Here is a solution. This will give performance and accuracy 100% (Time Complexity is O(N) or O(N * log(N)))

def solution(A):
    A = sorted(A)
    if list(range(1,len(A) + 1)) == A:
        return 1
    else:
        return 0
    pass

Schiff

Answer 40

Swift 100% solution:

public func solution(_ A : inout [Int]) -> Int {
    var a = Array(repeating: 0, count: A.count)

    for i in 0..<A.count {
        if A[i] < a.count + 1 {
            a[A[i] - 1] += 1
        } else {
            return 0
        }
    }

    for i in 0..<a.count {
        if a[i] != 1 {
            return 0
        }
    }

    return 1
}

Tem

Answer 41

class Solution
{
    public int solution(int[] A)
    { 
       int count=0;**strong text**
       int n=A.length;


       for(int j=1;j<n;j++)
       {
           if(A[j]>A[0])
           A[0]=A[j];
       } 


       if(A[0]==A.length)
       {
           for(int i=1;i<=A[0];i++)
           {
               for(int j=0;j<A[0];j++)
               {
                    if(A[j]==i)
                    count++;
                }
            }
        }
        else
            return 0;

       if(count==A[0])
           return 1;
       else
           return 0;
    }
}

Avalokitesvara

Please add text to explain your answer – Steinway