Intuition
Intuition\nThis problem seems simple but is tricky. The key idea is as follows:\n\n1. The nums array contains a maximum number m. \n2. For each number from 0 to
# Intuition\nThis problem seems simple but is tricky. The key idea is as follows:\n\n1. The nums array contains a maximum number m. \n2. For each number from 0 to m, we keep a track of the frequency of each one of them\n3. For any number n and p where p > n, the number of elements between n and p (inclusive) can be found in constant time using the prefix array approach on the frequency of elements\n4. The main idea is thus for for all the elements from 0 to m, if the frequency of the element is 0, we continue. Else, go for another loop where we multiply the number from 1 to max. Now for each multiplication, all the elements between max*k and max*(k+1) - 1 will have the same quotient k. We multiply the number of elements in the range by k to get the sum. We then multiply the sum with the frequency of the current number and add it to the result. We do this for all the numbers to get the result.\n\nEx: the current number is 2. All the numbers from 2 -3 will give 1, from 4-5 will give 2, from 6-7 will give 4 and so on\n\n\n# Approach\n\n# Complexity\n- Time complexity:\n$$O(N+Max)$$\n\n- Space complexity:\n$$O(Max)$$\n\n# Code\n```golang []\nvar MOD = 1_000_000_007\n\nfunc sumOfFlooredPairs(nums []int) int {\n\tn := len(nums)\n\n\tmax := -1\n\n\tfor i := 0; i < n; i++ {\n\t\tif nums[i] > max {\n\t\t\tmax = nums[i]\n\t\t}\n\t}\n\n\tfreqArr := make([]int, max+1)\n\n\tfor i := 0; i < n; i++ {\n\t\tfreqArr[nums[i]]++\n\t}\n\n\tprefixArr := make([]int, max+1)\n\n\tfor i := 1; i <= max; i++ {\n\t\tprefixArr[i] = prefixArr[i-1] + freqArr[i]\n\t}\n\n\tresult := 0\n\n\tfor j := 0; j <= max; j++ {\n\n        if freqArr[j] == 0 {\n            continue\n        }\n\n        sum := 0\n\t\tfor k := 1; k*j <= max; k++ {\n\t\t\tleft := k * j\n\t\t\tright := (k+1)*j - 1\n\n\t\t\tif right > max {\n\t\t\t\tright = max\n\t\t\t}\n\n\t\t\tnumNodes := prefixArr[right] - prefixArr[left-1]\n\n\t\t\tsum = (sum + (k * numNodes)) % MOD\n\t\t}\n\n        result = (result + freqArr[j] * sum) % MOD\n\t}\n\n\treturn result\n}\n```
['Go']