[Python] Sorting + Binary Search with thought process when being asked during interviews
Sorting + Binary Search\nMy strategy of resolving hard problems is to start with brute-force solution, and then improve it to sub/optimal approachs by identifyi
### Sorting + Binary Search\nMy strategy of resolving hard problems is to start with brute-force solution, and then improve it to sub/optimal approachs by identifying and fixing bottleneck.\nSo the brute-force approach for this problem is quite simple, we try out each possible pair of `nums[i], nums[j]` and calculate the total sum of floor, which obviously leads to TLE. Then we start to improve it by observations.\n\n**First Improvement**\nThe first observation is that the value of `floor(i, j) where i < j`is always `0`. So we can only care about the pair of `(i, j) where i > j`, which indicates that we need sort `nums` first. By sorting `nums`, for each `nums[i]`, we can get the floor value by `floor(nums[i], nums[j]) for j < i`. \n\n**Second Improvement**\nBut with this improvement, the time complexity is still *O(N^2)*, how we can improve it further? The reason that we still have *O(N^2)* time complexity is that we still check `floor(nums[i], nums[j])` for each `j` that is smaller than `i`. Can we speed up this process? yes, because we have sorted the `nums` already, we can get the index of number `nums[index]` that divided by `nums[i]` equals to `1`, `2`, `3` ... so on using binary search.\nFor example, we have checked `nums` as `[1,4,5,8,9]`, and we are at index `3` (8). So we can know that the index for `8` that divided by `8` equals to `1` is 3, and the index for `4` that divided by 8 equals to `2` is 1. Then all of numbers in the range `[index + 1:i]` have the same quotient, `[5, 8]` in this case. Then we can find the numbers in next quotient range of `[2: 3]`,  `[3: 4]` and so on. \nWhat\'s more, we can achieve better implementation by doing it in reverse way, multiplication instead of division. With the same example, we can check multiples for `4`, which are `[4, 8, 12]`.\n\n**Third Improvment**\nSo far, it seems a working solution, but it might still cause LTE because of duplicates. Then using counter is a common way to reduce complexity with duplicates. However, if we are doing this, the range counting we used in previous binary search doesn\'t work. We have to get the sum of numbers count in that range by checking the count for each number, which is still linear complexity. \nHow we can resolve problem of getting sum of subarray? It\'s prefix sum array.\n\n******\nThen put all together. \n1. Convert `nums` to `counter` (frequency)\n2. Sort the unique keys of `counter`.\n3. Create the prefix sum for the frequency.\n4. For interation of each key `i`, \n    1. We get the index for each multiple using binary search.\n    2. Get the sum of frequency of all numbers in `[index:  i]` using prefix sum array\n    3. Increase the `total` by multiplying the `counter[nums[i]]` with the sum\n5. Return the result.\n\n```python\ndef sumOfFlooredPairs(self, nums: List[int]) -> int:\n\tcounter = Counter(nums)\n    nums = sorted(counter.keys())\n    prefix = [0]\n    n = len(nums)\n    for i in range(n):\n\t\tprefix.append(prefix[-1] + counter[nums[i]])\n\n\ttotal = 0\n    for num in nums:\n\t\tfor mult in range(num, nums[-1] + 1, num):\n\t\t\tindex = bisect.bisect_left(nums, mult)\n            total += (prefix[-1] - prefix[index]) * counter[num]\n\treturn total % (10 ** 9 + 7)\n        \n```
[]