Tasks Details
The submission is being evaluated.
The submission is being evaluated.
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:
class Solution { public int solution(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 Java 21
Time spent on task 10 minutes
Notes
not defined yet
Code: 09:26:44 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int [] global_A;
public int solution(int[] A) {
// write your code in Java SE 8
global_A = A.clone();
return mergesort(global_A, 0, global_A.length-1);
}
public int mergesort(int[]A, int first, int last){
int mid = (first+last)/2;
int left_inver, right_inver;
if(first < last){
//Recursive calling
left_inver = mergesort(A, first, mid);
if(left_inver == -1)
return -1;
right_inver = mergesort(A, mid+1, last);
if(right_inver == -1)
return -1;
}
else{ // Terminate condition
return 0;
}
int first_index = first; // 왼쪽 부분값의 인덱스
int second_index = mid+1; // 오른쪽 부분의 인덱스
int[] temp = new int[last-first+1];
int temp_index = 0;
int merge_inver = 0; // inversion한 횟수
//왼쪽 인덱스의 위치가 mid보다 작고 오른쪽 인덱스 위치가 last보다 작을때까지 반복
while(first_index <= mid && second_index <= last){
// P < Q 에 해당하지 않기 때문에 inversion이 이루어 지지 않는 조합
if(A[first_index] <= A[second_index]){
temp[temp_index] = A[first_index];
first_index++;
}
else{
//인덱스 최대값이 작은 값에 해당하므로, inversion이 존재하는 경우
/* 예를들어
* [ 4, 5, 2, 3]
* [left part | right part]
* first_index가 현재 1이고, second_index가 3이고, mid가 2이면
* 여기서 필요한것은 2입니다. 그렇기 때문에 4,5를 inversion하지 않고 2로 접근해야합니다.
*
* 이후, 왼쪽 부분이 정렬이되고 , 모든 값들은 first_index 시작부터 끝까지 second_index보다 크게 됩니다.
* 그리고 그것보다 작은 indexes를 가지는 거죠
* 결과적으로 mid - first_index +1 이 출력되는 것입니다.
*/
temp[temp_index] = A[second_index];
second_index ++;
merge_inver += mid - first_index +1;
if(merge_inver > 1000000000)
return -1;
}
temp_index ++;
}
// while의 조건을 통해 inversion이 발생할 필요없는 부분을 지나치고
// 이후 inversion이 발생
// 왼쪽 부분의 값들은 왼쪽에 있는데 그것들은 작은 indexes값을 가지고 있습니다.
// 하지만 값은 크죠, 즉, inversion이 이루어 져야할 부분입니다.
// 주의해야할 것은 이러한 inversion횟수는 이미 계산되었습니다.
if(first_index != mid+1){
while(first_index <= mid){
temp[temp_index] = A[first_index];
first_index ++;
temp_index ++;
}
}
// 오른쪽 부분의 값들은 오른쪽에 있고, 이것들은 왼쪽의 값과 인덱스보다 높은 indexes와 값을 가지고 있습니다.
// 즉, inversion이 이루어지면 안되는 부분입니다.
if(second_index != last+1){
while(second_index <= last){
temp[temp_index] = A[second_index];
second_index ++;
temp_index ++;
}
}
// temp 배열에 넣었던 값들을 다시 A배열로 옮깁니다.
A = temp.clone();
if(merge_inver + left_inver + right_inver > 1000000000)
return -1;
else
return merge_inver + left_inver + right_inver;
}
}
Code: 09:32:56 UTC,
java,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int [] global_A;
public int solution(int[] A) {
// write your code in Java SE 8
global_A = A.clone();
return mergesort(global_A, 0, global_A.length-1);
}
public int mergesort(int[]A, int first, int last){
int mid = (first+last)/2;
int left_inver, right_inver;
if(first < last){
//Recursive calling
left_inver = mergesort(A, first, mid);
if(left_inver == -1)
return -1;
right_inver = mergesort(A, mid+1, last);
if(right_inver == -1)
return -1;
}
else{ // Terminate condition
return 0;
}
int first_index = first; // 왼쪽 부분값의 인덱스
int second_index = mid+1; // 오른쪽 부분의 인덱스
int[] temp = new int[last-first+1];
int temp_index = 0;
int merge_inver = 0; // inversion한 횟수
//왼쪽 인덱스의 위치가 mid보다 작고 오른쪽 인덱스 위치가 last보다 작을때까지 반복
while(first_index <= mid && second_index <= last){
// P < Q 에 해당하지 않기 때문에 inversion이 이루어 지지 않는 조합
if(A[first_index] <= A[second_index]){
temp[temp_index] = A[first_index];
first_index++;
}
else{
//인덱스 최대값이 작은 값에 해당하므로, inversion이 존재하는 경우
/* 예를들어
* [ 4, 5, 2, 3]
* [left part | right part]
* first_index가 현재 1이고, second_index가 3이고, mid가 2이면
* 여기서 필요한것은 2입니다. 그렇기 때문에 4,5를 inversion하지 않고 2로 접근해야합니다.
*
* 이후, 왼쪽 부분이 정렬이되고 , 모든 값들은 first_index 시작부터 끝까지 second_index보다 크게 됩니다.
* 그리고 그것보다 작은 indexes를 가지는 거죠
* 결과적으로 mid - first_index +1 이 출력되는 것입니다.
*/
temp[temp_index] = A[second_index];
second_index ++;
merge_inver += mid - first_index +1;
if(merge_inver > 1000000000)
return -1;
}
temp_index ++;
}
// while의 조건을 통해 inversion이 발생할 필요없는 부분을 지나치고
// 이후 inversion이 발생
// 왼쪽 부분의 값들은 왼쪽에 있는데 그것들은 작은 indexes값을 가지고 있습니다.
// 하지만 값은 크죠, 즉, inversion이 이루어 져야할 부분입니다.
// 주의해야할 것은 이러한 inversion횟수는 이미 계산되었습니다.
if(first_index != mid+1){
while(first_index <= mid){
temp[temp_index] = A[first_index];
first_index ++;
temp_index ++;
}
}
// 오른쪽 부분의 값들은 오른쪽에 있고, 이것들은 왼쪽의 값과 인덱스보다 높은 indexes와 값을 가지고 있습니다.
// 즉, inversion이 이루어지면 안되는 부분입니다.
if(second_index != last+1){
while(second_index <= last){
temp[temp_index] = A[second_index];
second_index ++;
temp_index ++;
}
}
// temp 배열에 넣었던 값들을 다시 A배열로 옮깁니다.
int copy_index = first;
for(int i=0; i <temp_index; i++){
A[copy_index] = temp[i];
copy_index++;
}
if(merge_inver + left_inver + right_inver > 1000000000)
return -1;
else
return merge_inver + left_inver + right_inver;
}
public static void main(String args[]){
Distinct d = new Distinct();
int [] A ={-1, 6, 3, 4, 7, 4};
System.out.println(d.solution(A));
}
}
Analysis
Code: 09:33:12 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int [] global_A;
public int solution(int[] A) {
// write your code in Java SE 8
global_A = A.clone();
return mergesort(global_A, 0, global_A.length-1);
}
public int mergesort(int[]A, int first, int last){
int mid = (first+last)/2;
int left_inver, right_inver;
if(first < last){
//Recursive calling
left_inver = mergesort(A, first, mid);
if(left_inver == -1)
return -1;
right_inver = mergesort(A, mid+1, last);
if(right_inver == -1)
return -1;
}
else{ // Terminate condition
return 0;
}
int first_index = first; // 왼쪽 부분값의 인덱스
int second_index = mid+1; // 오른쪽 부분의 인덱스
int[] temp = new int[last-first+1];
int temp_index = 0;
int merge_inver = 0; // inversion한 횟수
//왼쪽 인덱스의 위치가 mid보다 작고 오른쪽 인덱스 위치가 last보다 작을때까지 반복
while(first_index <= mid && second_index <= last){
// P < Q 에 해당하지 않기 때문에 inversion이 이루어 지지 않는 조합
if(A[first_index] <= A[second_index]){
temp[temp_index] = A[first_index];
first_index++;
}
else{
//인덱스 최대값이 작은 값에 해당하므로, inversion이 존재하는 경우
/* 예를들어
* [ 4, 5, 2, 3]
* [left part | right part]
* first_index가 현재 1이고, second_index가 3이고, mid가 2이면
* 여기서 필요한것은 2입니다. 그렇기 때문에 4,5를 inversion하지 않고 2로 접근해야합니다.
*
* 이후, 왼쪽 부분이 정렬이되고 , 모든 값들은 first_index 시작부터 끝까지 second_index보다 크게 됩니다.
* 그리고 그것보다 작은 indexes를 가지는 거죠
* 결과적으로 mid - first_index +1 이 출력되는 것입니다.
*/
temp[temp_index] = A[second_index];
second_index ++;
merge_inver += mid - first_index +1;
if(merge_inver > 1000000000)
return -1;
}
temp_index ++;
}
// while의 조건을 통해 inversion이 발생할 필요없는 부분을 지나치고
// 이후 inversion이 발생
// 왼쪽 부분의 값들은 왼쪽에 있는데 그것들은 작은 indexes값을 가지고 있습니다.
// 하지만 값은 크죠, 즉, inversion이 이루어 져야할 부분입니다.
// 주의해야할 것은 이러한 inversion횟수는 이미 계산되었습니다.
if(first_index != mid+1){
while(first_index <= mid){
temp[temp_index] = A[first_index];
first_index ++;
temp_index ++;
}
}
// 오른쪽 부분의 값들은 오른쪽에 있고, 이것들은 왼쪽의 값과 인덱스보다 높은 indexes와 값을 가지고 있습니다.
// 즉, inversion이 이루어지면 안되는 부분입니다.
if(second_index != last+1){
while(second_index <= last){
temp[temp_index] = A[second_index];
second_index ++;
temp_index ++;
}
}
// temp 배열에 넣었던 값들을 다시 A배열로 옮깁니다.
int copy_index = first;
for(int i=0; i <temp_index; i++){
A[copy_index] = temp[i];
copy_index++;
}
if(merge_inver + left_inver + right_inver > 1000000000)
return -1;
else
return merge_inver + left_inver + right_inver;
}
}
Analysis
Code: 09:34:31 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int [] global_A;
public int solution(int[] A) {
// write your code in Java SE 8
global_A = A.clone();
return mergesort(global_A, 0, global_A.length-1);
}
public int mergesort(int[]A, int first, int last){
int mid = (first+last)/2;
int left_inver, right_inver;
if(first < last){
//Recursive calling
left_inver = mergesort(A, first, mid);
if(left_inver == -1)
return -1;
right_inver = mergesort(A, mid+1, last);
if(right_inver == -1)
return -1;
}
else{ // Terminate condition
return 0;
}
int first_index = first; // 왼쪽 부분값의 인덱스
int second_index = mid+1; // 오른쪽 부분의 인덱스
int[] temp = new int[last-first+1];
int temp_index = 0;
int merge_inver = 0; // inversion한 횟수
//왼쪽 인덱스의 위치가 mid보다 작고 오른쪽 인덱스 위치가 last보다 작을때까지 반복
while(first_index <= mid && second_index <= last){
// P < Q 에 해당하지 않기 때문에 inversion이 이루어 지지 않는 조합
if(A[first_index] <= A[second_index]){
temp[temp_index] = A[first_index];
first_index++;
}
else{
//인덱스 최대값이 작은 값에 해당하므로, inversion이 존재하는 경우
/* 예를들어
* [ 4, 5, 2, 3]
* [left part | right part]
* first_index가 현재 1이고, second_index가 3이고, mid가 2이면
* 여기서 필요한것은 2입니다. 그렇기 때문에 4,5를 inversion하지 않고 2로 접근해야합니다.
*
* 이후, 왼쪽 부분이 정렬이되고 , 모든 값들은 first_index 시작부터 끝까지 second_index보다 크게 됩니다.
* 그리고 그것보다 작은 indexes를 가지는 거죠
* 결과적으로 mid - first_index +1 이 출력되는 것입니다.
*/
temp[temp_index] = A[second_index];
second_index ++;
merge_inver += mid - first_index +1;
if(merge_inver > 1000000000)
return -1;
}
temp_index ++;
}
// while의 조건을 통해 inversion이 발생할 필요없는 부분을 지나치고
// 이후 inversion이 발생
// 왼쪽 부분의 값들은 왼쪽에 있는데 그것들은 작은 indexes값을 가지고 있습니다.
// 하지만 값은 크죠, 즉, inversion이 이루어 져야할 부분입니다.
// 주의해야할 것은 이러한 inversion횟수는 이미 계산되었습니다.
if(first_index != mid+1){
while(first_index <= mid){
temp[temp_index] = A[first_index];
first_index ++;
temp_index ++;
}
}
// 오른쪽 부분의 값들은 오른쪽에 있고, 이것들은 왼쪽의 값과 인덱스보다 높은 indexes와 값을 가지고 있습니다.
// 즉, inversion이 이루어지면 안되는 부분입니다.
if(second_index != last+1){
while(second_index <= last){
temp[temp_index] = A[second_index];
second_index ++;
temp_index ++;
}
}
// temp 배열에 넣었던 값들을 다시 A배열로 옮깁니다.
int copy_index = first;
for(int i=0; i <temp_index; i++){
A[copy_index] = temp[i];
copy_index++;
}
if(merge_inver + left_inver + right_inver > 1000000000)
return -1;
else
return merge_inver + left_inver + right_inver;
}
}
Analysis
Compile error
Solution.java:108: error: cannot find symbol Distinct d = new Distinct(); ^ symbol: class Distinct location: class Solution Solution.java:108: error: cannot find symbol Distinct d = new Distinct(); ^ symbol: class Distinct location: class Solution 2 errors
Code: 09:34:39 UTC,
java,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107
// you can also use imports, for example:
// import java.util.*;
// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
int [] global_A;
public int solution(int[] A) {
// write your code in Java SE 8
global_A = A.clone();
return mergesort(global_A, 0, global_A.length-1);
}
public int mergesort(int[]A, int first, int last){
int mid = (first+last)/2;
int left_inver, right_inver;
if(first < last){
//Recursive calling
left_inver = mergesort(A, first, mid);
if(left_inver == -1)
return -1;
right_inver = mergesort(A, mid+1, last);
if(right_inver == -1)
return -1;
}
else{ // Terminate condition
return 0;
}
int first_index = first; // 왼쪽 부분값의 인덱스
int second_index = mid+1; // 오른쪽 부분의 인덱스
int[] temp = new int[last-first+1];
int temp_index = 0;
int merge_inver = 0; // inversion한 횟수
//왼쪽 인덱스의 위치가 mid보다 작고 오른쪽 인덱스 위치가 last보다 작을때까지 반복
while(first_index <= mid && second_index <= last){
// P < Q 에 해당하지 않기 때문에 inversion이 이루어 지지 않는 조합
if(A[first_index] <= A[second_index]){
temp[temp_index] = A[first_index];
first_index++;
}
else{
//인덱스 최대값이 작은 값에 해당하므로, inversion이 존재하는 경우
/* 예를들어
* [ 4, 5, 2, 3]
* [left part | right part]
* first_index가 현재 1이고, second_index가 3이고, mid가 2이면
* 여기서 필요한것은 2입니다. 그렇기 때문에 4,5를 inversion하지 않고 2로 접근해야합니다.
*
* 이후, 왼쪽 부분이 정렬이되고 , 모든 값들은 first_index 시작부터 끝까지 second_index보다 크게 됩니다.
* 그리고 그것보다 작은 indexes를 가지는 거죠
* 결과적으로 mid - first_index +1 이 출력되는 것입니다.
*/
temp[temp_index] = A[second_index];
second_index ++;
merge_inver += mid - first_index +1;
if(merge_inver > 1000000000)
return -1;
}
temp_index ++;
}
// while의 조건을 통해 inversion이 발생할 필요없는 부분을 지나치고
// 이후 inversion이 발생
// 왼쪽 부분의 값들은 왼쪽에 있는데 그것들은 작은 indexes값을 가지고 있습니다.
// 하지만 값은 크죠, 즉, inversion이 이루어 져야할 부분입니다.
// 주의해야할 것은 이러한 inversion횟수는 이미 계산되었습니다.
if(first_index != mid+1){
while(first_index <= mid){
temp[temp_index] = A[first_index];
first_index ++;
temp_index ++;
}
}
// 오른쪽 부분의 값들은 오른쪽에 있고, 이것들은 왼쪽의 값과 인덱스보다 높은 indexes와 값을 가지고 있습니다.
// 즉, inversion이 이루어지면 안되는 부분입니다.
if(second_index != last+1){
while(second_index <= last){
temp[temp_index] = A[second_index];
second_index ++;
temp_index ++;
}
}
// temp 배열에 넣었던 값들을 다시 A배열로 옮깁니다.
int copy_index = first;
for(int i=0; i <temp_index; i++){
A[copy_index] = temp[i];
copy_index++;
}
if(merge_inver + left_inver + right_inver > 1000000000)
return -1;
else
return merge_inver + left_inver + right_inver;
}
}