The Problem is focusing on unnecessary things

I believe that this exercise could give 100% just with 10^5, I made my solution, with a good complexity (N x logN), but due to the constant multiplier (5), it failed in 50% of cases in Java 8 , however in Java 15 it passed in 100% of cases, with the same solution, demonstrating that the problem was not logic in itself, but rather language details and micro optimization, as for example in the comments below people having to worry about something as specific as optimizing for 1, which I already find meaningless.

count 1 in the array but do not append to your array from the input

Solution for one

1*k <= max(k, x)

For 1st 1 in the array, there are n-1 pairs

For 2nd 1, there are more n-2 pairs

For 3rd 1, there are more n-3 pairs

...

For last 1, supposing there are k 1 in the array, there are more n-k pairs

ans_for_ones = n-1 + n-2 + n-3 + ... + n-k

= n*k - k*(k+1)/2

we will do divide and conquer algorithm and modify merge sort like this

• find max element
• find first index of the max element
• if the max element is side by side consecutively, find its last index too

# in merge_sort method
mx = max(arr[l:r + 1])
midleft = l
for i in range(l, r + 1):
    if arr[i] == midleft:
        midleft = i
        break
midright = midleft
while midright + 1 <= r and arr[midright + 1] == mx:
    midright += 1
merge_sort(l, midleft - 1)
merge_sort(midright + 1, r)

(sorted left_side) (max elements) (sorted right_side) [after using merge sort in smaller segments of the array]

=> (merge left_side and right_side) (max elements) = (sorted array)

For example:

4 1 3 5 1 12 12 12 12* 4 2 12 4 1

1 1 3 4 5 12 12 12 12* 1 2 4 4 12

i = midleft - 1
j = midright + 1
while i >= l and j <= r:
    if arr[i] * arr[j] <= mx:
        ans += i - l + 1 # arr[p] <= arr[i] for p<i, so arr[p]*arr[j] is also less than mx
        j += 1
    else:
        i -= 1

after everything

ans = ans + ans_for_ones

Full code: https://github.com/SR-Hossain/Coding-Platform-Problem-Solve/blob/main/LeetCode/Array%20Pairs.md

I got 100 points using pyhton 3. Some optimizations:

1. The number of pairs that can be formed using the value 1 in the array is known. We don't have to try to calculate the number of pairs with 1's, there is a simple formula for getting the number of all the pairs that contain 1
2. I created and kept track of a list of ranges which told how many pairs can be generated with the next value in the array.
3. The number of ranges for some of the tests were probably going up significantly so I got timeout failures, then I switched to binary search to find the range that the value falls in.

I feel like this solution should work, and it appears to be doing what I think it's doing, but it only passes some of the tests. I'd be interested in knowing if anybody sees what's theoretically wrong with it.

public static long solve(List<Integer> arr) {
        arr.sort(null); // assuming ok to mutate - easy to copy if not
        int maximum = arr.get(arr.size() - 1);
        long count = 0;
        
        for (int i = 0; i < arr.size(); i++) {
            int nextVal = arr.get(i);
            int cutoff = maximum / nextVal + 1; //exclusive
            if (cutoff <= nextVal) {
                break;
            }
            
            int cutoffIndex = Collections.binarySearch(arr, cutoff); //exclusive
            if (cutoffIndex < 0) {
                cutoffIndex = -(cutoffIndex + 1);
            }
            else {
                // seek to beginning of range of same value
                while (cutoffIndex >= 0 && arr.get(cutoffIndex) == cutoff) {
                    --cutoffIndex;
                }
                ++cutoffIndex;
            }
            count += cutoffIndex - i - 1;
        }
        
        return count;
    }

def solve (arr): # simple but slow - combining all mx = arr [0] #max (arr) res = 0 for j in range (1, len (arr)): mx = arr [j] if arr [j] > mx else mx for i in range (j): if (arr [i] * arr [j] <= mx): res += 1 return res