Tasks Details
medium
Compute number of inversion in an array.
Task Score
100%
Correctness
100%
Performance
100%
An array A consisting of N integers is given. An inversion is a pair of indexes (P, Q) such that P < Q and A[Q] < A[P].
Write a function:
int solution(vector<int> &A);
that computes the number of inversions in A, or returns −1 if it exceeds 1,000,000,000.
For example, in the following array:
A[0] = -1 A[1] = 6 A[2] = 3 A[3] = 4 A[4] = 7 A[5] = 4there are four inversions:
(1,2) (1,3) (1,5) (4,5)so the function should return 4.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C++
Time spent on task 1 minutes
Notes
not defined yet
Code: 09:28:22 UTC,
java,
autosave
Code: 09:28:27 UTC,
cpp,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
int merge(std::vector<int> &A, int begin, int middle, int end) {
std::vector<int> buffer(end - begin + 1);
int i = begin;
int j = middle + 1;
int k = 0;
int inversions = 0;
while (i <= middle && j <= end) {
if (A[i] <= A[j]) {
buffer[k] = A[i];
i++;
} else {
buffer[k] = A[j];
j++;
// ccomputing inversions
inversions += middle - i + 1;
}
k++;
}
while (i <= middle) {
buffer[k] = A[i];
k++;
i++;
}
while(j <= end) {
buffer[k] = A[j];
k++;
j++;
}
for (int i = 0; i < buffer.size(); ++i) {
A[i + begin] = buffer[i];
}
return inversions;
}
int mergeSort(std::vector<int> &A, int begin, int end) {
int result = 0;
if (begin < end) {
int middle = (begin + end) / 2;
int left_inversions = mergeSort(A, begin, middle);
if (left_inversions == -1) return -1;
int right_inversions = mergeSort(A, middle + 1, end);
if (right_inversions == -1) return -1;
int inversions = merge(A, begin, middle, end);
result = inversions + left_inversions + right_inversions;
if (result > 1'000'000'000) return -1;
}
return result;
}
int solution(std::vector<int> &A) {
int N = A.size();
int result = mergeSort(A, 0, N - 1);
return result;
}
Analysis
Code: 09:28:34 UTC,
cpp,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
int merge(std::vector<int> &A, int begin, int middle, int end) {
std::vector<int> buffer(end - begin + 1);
int i = begin;
int j = middle + 1;
int k = 0;
int inversions = 0;
while (i <= middle && j <= end) {
if (A[i] <= A[j]) {
buffer[k] = A[i];
i++;
} else {
buffer[k] = A[j];
j++;
// ccomputing inversions
inversions += middle - i + 1;
}
k++;
}
while (i <= middle) {
buffer[k] = A[i];
k++;
i++;
}
while(j <= end) {
buffer[k] = A[j];
k++;
j++;
}
for (int i = 0; i < buffer.size(); ++i) {
A[i + begin] = buffer[i];
}
return inversions;
}
int mergeSort(std::vector<int> &A, int begin, int end) {
int result = 0;
if (begin < end) {
int middle = (begin + end) / 2;
int left_inversions = mergeSort(A, begin, middle);
if (left_inversions == -1) return -1;
int right_inversions = mergeSort(A, middle + 1, end);
if (right_inversions == -1) return -1;
int inversions = merge(A, begin, middle, end);
result = inversions + left_inversions + right_inversions;
if (result > 1'000'000'000) return -1;
}
return result;
}
int solution(std::vector<int> &A) {
int N = A.size();
int result = mergeSort(A, 0, N - 1);
return result;
}
Analysis
Code: 09:28:38 UTC,
cpp,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
int merge(std::vector<int> &A, int begin, int middle, int end) {
std::vector<int> buffer(end - begin + 1);
int i = begin;
int j = middle + 1;
int k = 0;
int inversions = 0;
while (i <= middle && j <= end) {
if (A[i] <= A[j]) {
buffer[k] = A[i];
i++;
} else {
buffer[k] = A[j];
j++;
// ccomputing inversions
inversions += middle - i + 1;
}
k++;
}
while (i <= middle) {
buffer[k] = A[i];
k++;
i++;
}
while(j <= end) {
buffer[k] = A[j];
k++;
j++;
}
for (int i = 0; i < buffer.size(); ++i) {
A[i + begin] = buffer[i];
}
return inversions;
}
int mergeSort(std::vector<int> &A, int begin, int end) {
int result = 0;
if (begin < end) {
int middle = (begin + end) / 2;
int left_inversions = mergeSort(A, begin, middle);
if (left_inversions == -1) return -1;
int right_inversions = mergeSort(A, middle + 1, end);
if (right_inversions == -1) return -1;
int inversions = merge(A, begin, middle, end);
result = inversions + left_inversions + right_inversions;
if (result > 1'000'000'000) return -1;
}
return result;
}
int solution(std::vector<int> &A) {
int N = A.size();
int result = mergeSort(A, 0, N - 1);
return result;
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N))
expand all
Correctness tests
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK