11

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.

1
  • 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 ?
    – gmuhammad
    Dec 15, 2014 at 22:31

40 Answers 40

1
2
0

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

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
1
  • Hi, this doesn't solve the question from the user. He clearly didn't ask for a solution but for an explanation. Jun 6, 2020 at 17:00
0

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))

0

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

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;
}
1
  • 1
    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. Dec 17, 2020 at 10:04
0

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;
    }
}
1
  • 1
    Please edit your answer to explain what was wrong with the code in the question.
    – Null
    Mar 17, 2021 at 12:33
0

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

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
-1
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;
    }
}
1
  • Please add text to explain your answer Dec 3, 2015 at 6:22
1
2

Not the answer you're looking for? Browse other questions tagged or ask your own question.