Guest User

Untitled

a guest
Jan 14th, 2020
61
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