Codility PermCheck Solution isn't working on a few data sets

Question

Trying to solve codility lessons for practice and working on this.

Written my code in Java and tested the code on a wide range of inputs, however the code fails for extreme_min_max, single and double in the codility test results.

Assumption given:

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

Explanation of my code:
1. Sort the given array.
2. Iterate over each element in the array to find the difference between every consecutive pair. If the difference is not 1, Then its not a perm hence return 0. In case there is only one element in the array, return 1.

Can anyone please help me find out the bug(s) in my code?

My code:

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

    Arrays.sort(A);
    for (int i = 0; i < A.length-1; i++)
    {
        long diff = Math.abs(A[i] - A[i+1]);
        if(diff!=1)
            return 0;
    }
    return 1;
}

Answer 1

Here is simple and better implementation which runs in O(N) time complexity and takes O(N) space complexity.

public int solution(int[] A)
{ 
    int size = A.length;
    int hashArray[] = new int[size+1];

    for (int i = 0; i < size; i++)
    {
        if(A[i]>size)
            return 0;
        else
            hashArray[A[i]]+=1;
    }
    for(int i=1;i<=size;i++)
    if(hashArray[i]!=1)
    return 0;

    return 1;
}

Answer 2

Try this in C# (Score 100%) :

using System;
using System.Linq;

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

     if (A.Any(x => x == 0)) { return 0; }
         var orderSelect = A.OrderBy(x => x).GroupBy(x => x);
         if (orderSelect.Any(x => x.Count() > 1)) { return 0; }
         var res = Enumerable.Range(1, A.Length).Except(A);
         return res.Any() ? 0 : 1;           
    }
  }

Answer 3

Pretty simple:

Your code doesn't check this condition:

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

Ensure that the first element after sorting is 1, and everything should work.

Answer 4

I'm not big on Java syntax, but what you want to do here is:

1. Create an array temp the length of A - initialized to 0.
2. Go over A and do temp[A[i]]++.
3. Go over temp, and if any place in the array is not 1, return false.

Answer 5

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;

}

Answer 6

Here's my first 100% code. I can't say if it's the fastest but it seems all correct -- watch the double OR ( || ) condition.

import java.util.Arrays;

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

      int i = 0;
      int size = A.length;

      if ( size > 0 && size < 100001)
      {
          // Sort the array ascending:
          Arrays.sort(A);

          // Check each element:
          for(i = 0; i < size; i++)
             if ( A[i] > size || A[i] != (i + 1) )
                return 0;
          return 1;
      }
      return 0;
   }
}

EDIT Actually, we need not worry about valid first element data (i.e. A[i] > 0) because, after sorting, a valid perm array must have A[0] = 1 and this is already covered by the condition A[i] = i + 1. The upper limit for array entries (> 1,000,000,000) is restricted further by the limit on the array size itself (100,000) and we must check for conformity here as there will be a Codility test for this. So I have removed the lower limit condition on array entries.

Answer 7

Below code runs and gave me a 100%, the time complexity is O(n):

    private static int solution(int[] A) {
    int isPermutation = 1; // all permutations start at 1
    int n = A.length;
    Arrays.sort(A);

    if (n == 0) return 0; // takes care of edge case where an empty array is passed

    for (int i = 0; i < n; i++) {
        if (A[i] != isPermutation) { //if current array item is not equals to permutation, return 0;
            return 0;
        }
        isPermutation++;
    }
    return 1;
}

Answer 8

100% score with complexity O(N)

 public int solution(int[] A) {
     int res = 1;
    
    if (A.length == 1 && A[0]!=1)
        return 0;
    
    int[] B = new int[A.length];
    for (int j : A) {
        int p = j - 1;
        if (A.length > p)
            B[p] = j;
    }

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