>90%, >45%, c++ solution with explanation
According to the hints, my idea is the following :\n\n 1. Iterate over nums in order to find the maximum value max_n.\n 2. Create an array of occurences occs of
According to the hints, my idea is the following :\n\n* 1. Iterate over `nums` in order to find the maximum value `max_n`.\n* 2. Create an array of occurences `occs` of size `max_n + 1` (no need to have it of size 10<sup>5</sup> if we only have numbers in range `0` to `max_n`.\n* 3. Iterate over `occs` to create the array of cumulated occurences according to prefix sum algorithm.\n\nFor example, if we have the following input : `[4,2,3,5,6,5,7,4]`,  with max value `7`, we will obtain :\n\n||0|1|2|3|4|5|6|7|\n|:-| :-: |:-:| :-:| :-:| :-:| :-:| :-:|-:|\n| occs |0|0|1|1|2|2|1|1|\n|occs_acc|0|0|1|2|4|6|7|8\n\nThe sorted arry of our input is `[2,3,4,4,5,5,6,7]`. Having noticed that `floor(i/j) = 0` if `j>i`,brute force solution would still be O(n<sup>2</sup>) cause we would have to test all couples `(i, j)` with `j <= i`, which is easy in a sorted array. With the solution explained above, we can optimize this complexity. We proceed by checking only the multiples of a given value. The array `occs_acc` allow us to know how many numbers are between two different multiples. For example, if we deal from left to right in sorted array (which is in a way already made with a bucket sort in `occs`) and are treating the value `3` with the first multiple `k = 1`, there will be 5 values that will give a floor of 1 :\n\n`3/3, 4/3, 4/3, 5/3, 5/3`\n\nWe can know that number by looking in `occs_acc` at indices `5 = ((k+1)*3 - 1)` and `2 = (k*3 - 1)`.  This is because `occs_acc[5]` is the total numbers in input array that are less than `6`, which is the next multiple of `3` and same for `occs_acc[2]`. So, by subtracting those values, we have the exact total occurences of numbers which give a floor of `1` by dividing `3`. To update the sum correctly, we still have to multiply this difference by the number of occurences of number `3`, because it applies for each one of them. In our case, this number is `1`.\n\nWe then iterate this procedure with the multiple `2` and so on, until we have reached the end of the array...\n\nThis solution is satisfying but not perfect, because we may have a lot of `0` in the array of occurences, which could cause extra computations in the last loop. Maybe a map or another data structure could be better but I don\'t know...\n\nThank you for reading \n\n```\nclass Solution {\n    \nprivate:\n    \n    int MOD = 1e9 + 7;\n    \npublic:\n    \n    int sumOfFlooredPairs(vector<int>& nums) {\n\n        // first of all, we record the max value\n        int max_n = INT_MIN;\n        for(int n : nums) max_n = max(max_n, n);\n        \n        // then the occurences for each number in [0, max]\n        vector<int> occs(max_n + 1, 0);\n        for(int n : nums) occs[n]++;\n        \n        // prefix sum algorithm to accumulate the occurences\n        vector<int> occs_acc(max_n + 1, 0);\n        for(int i = 1; i < max_n + 1; ++i) {\n            occs_acc[i] = occs[i] + occs_acc[i - 1]; \n        }\n        \n        // long long needed to prevent overflows\n        long long ans = 0; \n        for(int i = 0; i < max_n + 1; ++i) {\n            \n            // just handle numbers that occur at least once\n            if(occs[i] != 0) {\n                                \n                int k = 1;\n                int k_next;\n                \n                // for each multiple of i\n                do {\n                    \n                    k_next = k + 1;\n\n                    // "right and left" multipliers in occs_acc \n                    int r = min(k_next * i - 1, max_n);\n                    int l = k * i - 1;\n                    \n                    ans += ((long long) occs_acc[r] - (long long) occs_acc[l]) * (long long) occs[i] * k++;\n                    \n                    \n                } while(k_next * i - 1 < max_n);\n            }\n        }\n        \n        return ans % MOD;\n    }\n};\n```
['C', 'Bucket Sort', 'Prefix Sum']