C++ Prefix Sums + Iterate over Element Values
The naive solution to this problem would have a runtime complexity of O(n^2), which results in a TLE for an array size of at most 1e5. However, note the other p
The naive solution to this problem would have a runtime complexity of O(n^2), which results in a TLE for an array size of at most 1e5. However, note the other problem size constraint: 1 <= nums[i] <= 1e5. The range of element value is limited, giving us the idea of iterating all possible element values and sum up their their contributions to the result, instead of summing up the results of elements. Note floor(m/n) takes the value of 1 when  n <= m < 2*n, 2 when 2*n <=\nm < 3 * n, etc. So to calculate the sum of all floor pair floor(m/n)s where n is known, we only need to find out the number of elements n <= m < 2 *n, 2*n <=m\n< 3*n, etc. From these observations, we can form a rough idea of the problem\'s solution:\n\n1. Find out the number of elements in nums with values 1, 2, 3, ....\n2. Implement a data structure to quickly retrieve the number of element in a certain range. A prefix sum array would suffice.\n3. For each possible *value* n of the elements, find out sum of all floor pair floor(m/n)s. We can use the prefix sum array to find out the number of ms that are between n and 2n, 2n and 3n, 3n and 4n, etc, and add their contributions together.\n\n```\nclass Solution {\npublic:\n    int sumOfFlooredPairs(vector<int>& nums) {\n        // freq[i] = number of elements with value i\n        vector<int> freq(100001, 0);\n        // prefix_freq[i] = number of elements whose values are between 1 to i inclusive\n        vector<int> prefix_freq(100002, 0); \n        // mx = maximum element\n        int mx = -1;\n        for(int n : nums) {\n            freq[n]++;\n            mx = max(mx, n);\n        }\n        // build prefix sum array\n        prefix_freq[1] = freq[1];\n        for(int i = 2; i < freq.size(); i++) {\n            prefix_freq[i] = freq[i] + prefix_freq[i-1];\n        }\n        // cnt_sum(start, end) = number of elements between start and end\n        auto cnt_sum = [&](int start, int end) {\n            if(start == 1) return prefix_freq[end];\n            else return prefix_freq[end] - prefix_freq[start - 1];\n        };\n        int res = 0;\n        for(int i = 1; i <= mx; i++) {\n            // contribution of sum of floor(m/i)\n            int val = 1;\n            while(true) {\n                int start = val * i;\n                int end = (val + 1) * i - 1;\n                if(end >= mx) end = mx;\n                res += (val * freq[i] * cnt_sum(start, end));\n                res %= 1000000007;\n                if(end == mx) break;\n                val++;\n            }\n        }\n        return res;\n    }\n};\n```\n\n
[]