Problem statement

https://leetcode.com/problems/sum-of-floored-pairs/

Solution

Imagine for the moment that we have M = 20 and consider number num = 3. Then let us look at all numbers divisible by 3 and create array [0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0] then transform it to accumulate sums:

acc = [0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6]

Now, this list has the property that acc[i] = i//3

If we have now m = 5, then we have acc = [0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4]. If we sum these two accumulative sums we will have the same result as if we first upate elements for m = 3 and m = 5 and then apply accumulate. What we have now in acc[i] = i//3 + i//5. So, it is enough to update incs for all elements from nums: better to do it for counters, no need to update each time for [3,3,3,3,3,3,3,5,5,5], we can do it one time for 3 with frequency 6 and one time for 5 with frequency 3. Then we traverse acc and choose only those elements we need, not all of them, but only those which we have in nums: here we again can use trick with counter.

Complexity

Time complexity is O(M*log M + n), where n = len(nums) and M = max(nums)

Code

class Solution:
    def sumOfFlooredPairs(self, nums):
        M = max(nums)
        incs, cnt = [0]*(M+1), Counter(nums)           
        for num, freq in cnt.items():                                     
            for j in range(num, M+1, num):               
                incs[j] += freq
        acc = list(accumulate(incs))
        return sum([acc[num]*f for num, f in cnt.items()]) % (10**9 + 7)