Tasks Details
easy
1.
PermCheck
Check whether array A is a permutation.
Task Score
100%
Correctness
100%
Performance
100%
A non-empty 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] = 2is a permutation, but array A such that:
A[0] = 4 A[1] = 1 A[2] = 3is 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 an 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] = 2the function should return 1.
Given array A such that:
A[0] = 4 A[1] = 1 A[2] = 3the function should return 0.
Write an efficient algorithm for the following assumptions:
- 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].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 8
Time spent on task 1 minutes
Notes
not defined yet
Code: 08:59:26 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
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;
}
}
Analysis
Code: 08:59:33 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
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;
}
}
Analysis
Code: 08:59:38 UTC,
java,
final,
score:
100
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
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;
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
1.447 s
OK
2.
1.444 s
OK
1.
1.446 s
OK
2.
1.442 s
OK
1.
1.458 s
OK
2.
1.410 s
OK
3.
1.492 s
OK
4.
1.490 s
OK
1.
1.464 s
OK
2.
1.463 s
OK
3.
1.445 s
OK
4.
1.454 s
OK
1.
1.455 s
OK
2.
1.466 s
OK
expand all
Performance tests
1.
1.474 s
OK
2.
1.498 s
OK
1.
1.686 s
OK
2.
1.847 s
OK
1.
1.844 s
OK
2.
1.815 s
OK
1.
1.835 s
OK
2.
1.781 s
OK
1.
1.459 s
OK
2.
1.596 s
OK
3.
1.472 s
OK