'Codility PermCheck why my solution is not working
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.
Solution 1:[1]
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.
Solution 2:[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;
}
Solution 3:[3]
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
Solution 4:[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;
}
}
Solution 5:[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
Solution 6:[6]
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;
}
}
Solution 7:[7]
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;
}
}
Solution 8:[8]
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
Solution 9:[9]
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;
}
Solution 10:[10]
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;
}
Solution 11:[11]
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.
Solution 12:[12]
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.
Solution 13:[13]
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;
}
Solution 14:[14]
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
Solution 15:[15]
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;
};
Solution 16:[16]
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
Solution 17:[17]
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;
}
}
Solution 18:[18]
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/
Solution 19:[19]
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)...
Solution 20:[20]
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;
}
}
Solution 21:[21]
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;
}
Solution 22:[22]
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).
Solution 23:[23]
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;
}
Solution 24:[24]
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))
Solution 25:[25]
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
}
Solution 26:[26]
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
}
Solution 27:[27]
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;
}
Solution 28:[28]
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
}
Solution 29:[29]
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;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow