Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public long count(int[] arr, int n, long count) {
- if(n == 0) {
- return 0;
- }
- if(n == 1) {
- int max = Math.max(arr[0], arr[1]);
- if(arr[0] * arr[1] <= max) {
- return 1;
- }
- else {
- return 0;
- }
- }
- int max = arr[1];
- int maxIndex = 1;
- for (int i = 0; i < n; i++) {
- if (arr[i] > max) {
- max = arr[i];
- maxIndex = i;
- }
- }
- int[] rightSub = Arrays.copyOfRange(arr, 0, maxIndex + 1);
- int[] leftSub = Arrays.copyOfRange(arr, maxIndex, arr.length);
- Arrays.parallelSort(rightSub);
- Arrays.parallelSort(leftSub);
- int i = 0;
- int j = rightSub.length-1;
- while (i < j) {
- if (rightSub[i] * rightSub[rightSub.length - 1] <= max) {
- count = count + j - i;
- i++;
- } else {
- j--;
- }
- }
- i = 0;
- j = leftSub.length-1;
- while (i < j) {
- if (leftSub[i] * leftSub[leftSub.length - 1] <= max) {
- count = count + j - i;
- i++;
- } else {
- j--;
- }
- }
- return count(rightSub, rightSub.length-1,count) + count(leftSub, leftSub.length-1,count);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement