We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Trees
  4. Array Pairs
  5. Discussions

Array Pairs

  • davidpet
     + 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;
    }