Codility PermCheck Why My Solution Doesn't Work

Question

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

[Change] Description of the problem:

Given a non-empty zero-indexed array A, consisting of N integers. A permutation is a sequence containing each element from 1 to N once and only once. For example, an array A such that:

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

this is a permutation, but an array A such that:

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

not a permutation because the value 2 is missing. The goal is to check if array A is a permutation. Write a function: class Solution {public int solution (int [] A); , A , :

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

the function should return 1. The given array A is such that:

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

the function should return 0. Suppose that: N is an integer in the range [1..100,000]; each element of array A is an integer in the range [1..1 000 000 000].

My solution at the moment:

 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 expect. I know there are many solutions, but I want to know what the problem is with my solution. What corner cases I miss. The input list does not display on the results page in which the above solution fails.

Answer 1

The reason this doesn't work is because permutation (as explained) is not the only way to get a certain amount, as your decision suggests. For instance:

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

In accordance with the description of the problem, as written, I do not think that this means that the data does not have duplicates.

Answer 2

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 3

You can simply add them to the set and check the length at the end. If any of the values ​​in the list is larger than the size of the list, you can advance in advance, since it will never be a valid resolution.

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

Answer 4

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

Answer 5

Javascript solution with 100% results:

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

Answer 6

If there is a duplicate - return 0 I implemented with a 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 7

Here is a solution in java 100% coding.

 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 8

C ++ score: 100.

The idea is that we will create a new array B with N+1 elements and all false , then set B[A[i]] = true . Iterate over B if we find that B[i] is false then returns 0 , otherwise 1 .

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

Answer 9

My solution In Python, I hope this helps.

  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 

Answer 10

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

Answer 11

Here 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 complexity of time is O (2n), which is O (n). https://codility.com/demo/results/training4YUHYS-HDW/

Answer 12

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

However, I think the worst time complexity would be O (nlgn) due to sorting.

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

Answer 13

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

Answer 14

20% performance rating.

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

Answer 15

Codility is a little silly 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 does not have to pass a performance test - it is O (n * logn) due to sorting, so it is worse than O (n).

Answer 16

100% simple solution

 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 the point to stop //checking and return as per the boolean value set if (!set.contains(i)) { numberNotFound = true; break; } } return numberNotFound ? 0 : 1; } 

Answer 17

I believe all sort-dependent decisions are wrong! Because the required time complexity is O (N); and sorting cannot be O (N).

* oh and my python solution

 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 not a permutation # if i appeared before in A, then the hole[i] should be 1, in such case it not a permutation as well if i>len(A) or holes[i]==1: return 0 holes[i] = 1 return 1 

Answer 18

I think that as the head of the count elements, the desired solution is to use the count of the elements and then check to see if each element is exactly once in the buckets array. My Swift solution looks like this. But not tested 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)) 

Answer 19

I understand that since this tutorial requires O (n), so the solution should be without sorting. the permutation keyword is a sequence and from 1 to N only once. therefore, the solution should check for duplicates and all elements in the 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 did not pass extreme_min_max and single tests, I don’t know why, since the code checks if the length of the array is A 1, just return 1.

Answer 20

Solution in PHP with 100% in 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 } 

Answer 21

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 } 

Answer 22

My JavaScript solution got 100 in all directions. Essentially, I run the array once and make each value an index in a new array with the value set to true (or wtv if it's true). In doing so, I check to see if any value has already been entered into the new array. Then I iterate over the array and immediately return 0 if any element is false. I suppose close enough to O (2n).

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

Answer 23

This is my decision

 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 } 

^ terrific.

Answer 24

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

 def solution(A): # write your code in Python 3.6 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 

Answer 25

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