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.

Answer 1

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;
 }
}

Answer 2

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.

Answer 3

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.

Answer 4

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;
}

Answer 5

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