Java: Sorting with Divide and Conquer
This solution is not the fastest. It takes 1141ms but uses a different approach than what is mentioned in other posts that utilize a frequency and prefix array.
This solution is not the fastest. It takes 1141ms but uses a different approach than what is mentioned in other posts that utilize a frequency and prefix array.\n\nFirst, we sort the array because that doesn\'t change the answer or time complexity and lets us use previous computations for repeated elements. Then starting from the leftmost element `a_i`, we find `a_i/a_i + a_i+1/a_i + ... + a_n/a_i` for all `a_i`. We solve this recursively by breaking into smaller sub problems. See `findSum()` method to see how the recursion works.\n\nSpace: Due to recursion the space is `O(n)` in the recursion stack when numbers are `[1,2,3, ... , n]`.\nTime: The worst case is achieved when numbers are again `[1,2,3, ... , n]`. In this case, it is `O(n + n-1/2 + n-2/3 + ... + 1/n) = O(nlogn)` Sorting in the beginning doesn\'t change this.\n\n```\nclass Solution {\n    final int mod = 1_000_000_007;\n    \n    // Returns sum of nums[i]/div for from<=i<=to.\n    private int findSum(int[] nums, int from, int to, int div) {\n        if (from > to) return 0;\n        if (from == to) return nums[from] / div;\n        if (nums[to] / div == nums[from] / div) {\n            return (int)(((to - from + 1) * (long)(nums[to] / div)) % mod);\n        }\n        int mid = from + (to - from)/2;\n        return (findSum(nums, from, mid, div) + findSum(nums, mid + 1, to, div)) % mod;\n    }\n    \n    public int sumOfFlooredPairs(int[] nums) {\n        int len = nums.length;\n        if (len == 0) return 0;\n        \n        // Sorting makes the problem simple.\n        Arrays.sort(nums);\n        \n        int total = 0;\n        // Duplicates should be handled separately. We cannot ignore the previous numbers that are same.\n        int prevNum = -1;\n        int prevTotal = -1;\n        for (int i=0 ; i<len ; ++i) {\n            if (nums[i] == prevNum) {\n                total += prevTotal;\n            } else {\n                prevTotal = findSum(nums, i, len-1, nums[i]);\n                prevNum = nums[i];\n                total += prevTotal;\n            }\n            total %= mod;\n        }\n        return total;\n    }\n}\n```
[]