Task description
A zero-indexed array A consisting of N integers is given. An inversionis a pair of indexes (P, Q) such that P < Q and A[Q] < A[P].
Write a function:
the number of inversions in A, or returns −1 if it exceeds 1,000,000,000.
Assume that:
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.
Complexity:
Analysis
Write a function:
thatCOMPUTESclass Solution { public int solution(int[] A); }
the number of inversions in A, or returns −1 if it exceeds 1,000,000,000.Assume that:
For example, in the following array:
- 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].
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.
Complexity:
Elements of input arrays can be modified.
- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
// 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");
import java.math.BigDecimal;
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
int len=A.length;
int count=0;
int i=0;
int j=0;
while(i<len){
j=i+1;
while(j<len){
if(A[i]>A[j]){
count++;
}
j++;
}
i++;
}
if(count>1000000000) count=-1;
return count;
}
}
Analysis summary
The following issues have been detected: timeout errors.
Detected time complexity:
O(N**2)
O(N**2)
expand allExample tests
expand allCorrectness tests
expand allPerformance tests
big_monotonic
long descending and non-ascending sequence
long descending and non-ascending sequence
TIMEOUT ERROR
running time: >8.00 sec., time limit: 2.97 sec.
running time: >8.00 sec., time limit: 2.97 sec.
Comments
Post a Comment