SHARE
TWEET

Untitled

a guest Jan 14th, 2020 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public long count(int[] arr, int n, long count) {
  2.  
  3.         if(n == 0) {
  4.             return 0;
  5.         }
  6.         if(n == 1) {
  7.             int max = Math.max(arr[0], arr[1]);
  8.             if(arr[0] * arr[1] <= max) {
  9.                 return 1;
  10.             }
  11.             else {
  12.                 return 0;
  13.             }
  14.         }
  15.        
  16.  
  17.         int max = arr[1];
  18.         int maxIndex = 1;
  19.        
  20.         for (int i = 0; i < n; i++) {
  21.             if (arr[i] > max) {
  22.                 max = arr[i];
  23.                 maxIndex = i;
  24.             }
  25.         }
  26.  
  27.         int[] rightSub = Arrays.copyOfRange(arr, 0, maxIndex + 1);
  28.         int[] leftSub = Arrays.copyOfRange(arr, maxIndex, arr.length);
  29.  
  30.         Arrays.parallelSort(rightSub);
  31.         Arrays.parallelSort(leftSub);
  32.  
  33.         int i = 0;
  34.         int j = rightSub.length-1;
  35.         while (i < j) {
  36.             if (rightSub[i] * rightSub[rightSub.length - 1] <= max) {
  37.                 count = count + j - i;
  38.                 i++;
  39.             } else {
  40.                 j--;
  41.             }
  42.         }
  43.  
  44.         i = 0;
  45.         j = leftSub.length-1;
  46.         while (i < j) {
  47.             if (leftSub[i] * leftSub[leftSub.length - 1] <= max) {
  48.                 count = count + j - i;
  49.                 i++;
  50.             } else {
  51.                 j--;
  52.             }
  53.         }
  54.  
  55.         return count(rightSub, rightSub.length-1,count) + count(leftSub, leftSub.length-1,count);
  56.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top