PermCheck Solution
Task
The task is to calculate if an array contains all the numbers from 1 to N, where N is the size of the array:
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:
int solution(vector<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].
Solution 1
The naive solution of searching for each number [1..N] in the array would be O(N2).
The most time efficient solution is to use a bit map, this is O(N).
#include <iostream>
using namespace std;
#include <bitset>
#include <vector>
#define SIZEA 1000000000
int solution(vector<int> &A) {
auto pbits = new bitset<SIZEA>;
pbits->reset();
for (size_t i = 0; i < A.size(); i++) {
int el = A[i];
if ((*pbits)[el]) {
return 0;
}
(*pbits)[el] = true;
}
for (uint i = 0; i < A.size(); i++) {
if (!(*pbits)[i+1]) {
return 0;
}
}
return 1;
}Line 9 would be a memory leak if the function was called repeatedly.
Results
Codility Results
| Correctness | 100% |
| Performance | 100% |
| Time Complexity | O(N) |
Solution 2
An even simpler solution is to first sort the array. This is O(N*log(N)), but also passes the performance test.
int solution(vector<int> &A) {
std::sort(std::begin(A), std::end(A));
for (size_t i = 0; i < A.size(); i++) {
if(A[i] != i+1) return 0;
}
return 1;
}Results
| Correctness | 100% |
| Performance | 100% |
| Time Complexity | O(N*log(N)) |
Test Function
This code tests the solution
int main() {
vector<int> v1{4, 1, 3, 2};
assert(solution(v1) == 1);
vector<int> v2{4, 1, 3};
assert(solution(v2) == 0);
vector<int> v3{4, 1, 3,3,2};
assert(solution(v3) == 0);
vector<int> v4{1};
assert(solution(v4) == 1);
vector<int> v5{2};
assert(solution(v5) == 0);
vector<int> v6{12, 9, 3, 2};
assert(solution(v6) == 0);
return 0;
}Other Solutions
These are some other solutions to this problem on the web
This blog has an apparently clever solution:
int solution(vector<int> &v) {
unsigned xorsum = 0;
int v_size = v.size();
for (size_t i = 0; i < v_size; i++) {
xorsum = (i + 1) ^ static_cast<unsigned>(v[i]) ^ xorsum;
}
return xorsum == 0;
}This works (mostly) because:
- XORing a number with itself = 0
- XOR is commutative, so a ^ b ^ c ⇔ c ^ b ^ a
And so
xorsum ⇔ (1 ^ v[a] ) ^ (2 ^ v[b]) ^ … for every possible permutation of a,b,c, …So if a permutation exists for which v[a]=1, v[b]=2 etc, then xorsum == 0
However, there are other arrays for which xorsum also == 0. For example, this solution fails the test above with array v6.
The Codility tests do not contain any test data for which this fails, so it passes the test with 100% correctness.
| Correctness | 100% |
| Performance | 100% |
| Time Complexity | O(N) |
These blogs also have some variation of the bit set solution above
- The bit set solution in Python and Java.
- A variation in Java that stores the values in a HashSet instead of a bit set.
- Another variation in C++. Rather than directly testing for missing values, this relies on the fact that if there are any values > A.size() there must be corresponding missing values and so avoids a second loop through the array.