• + 1 comment

    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;
        }