✅ C++ Short & Easy | Frequency Prefix Sum Solution w/ Explanation
\u2714\uFE0F Solution (Frequency Prefix Sum)\n\nWe can\'t iterate sum up for all the possible pairs since the given constraints would lead to TLE. \n\nWe need t
\u2714\uFE0F ***Solution (Frequency Prefix Sum)***\n\nWe can\'t iterate sum up for all the possible pairs since the given constraints would lead to TLE. \n\nWe need to observe that the result of *`floor(nums[i] / nums[j])`*,  will be - \n\n* **`0`** if `nums[i] < nums[j]`\n* **`1`** if `nums[j] <= nums[i] < (2 * nums[j])`\n* **`2`** if `2 * nums[j] <= nums[i] < (3 * nums[j])`\n* and so on...\n\nWe can use this to build a **frequency array** and then **calculate the prefix sum of it**. \n\nAfter this, for every *`num`* in *`nums`*, we will add the answer into *`sum`* as per the above observation. \n\n* All the numbers in the range `[0, num - 1]` will contribute **0** to the sum each. The **frequency of numbers in this range** will be given by *`freq[num - 1] - freq[0]`*.\n* All the numbers in the range `[num, 2*num - 1]` will contribute **1** to the sum each. **Frequency:** *`freq[num] - freq[2num - 1]`*.\n* Numbers in `[2*num, 3*num - 1]` will contribute **3** each. **Frequency:**  *`freq[2num] - freq[3num - 1]`*.\n* And so on till our range covers the maximum element of the *`nums`* array...\n\n**C++**\n```\nconst int MAXN = 1e5 + 1, MOD = 1e9 + 7;\nint sumOfFlooredPairs(vector<int>& nums) {\n\tvector<long> freq(2*MAXN+1);        \n\tlong mx = 0, sum = 0;\n\tfor(auto num : nums) ++freq[num], mx = max((int)mx, num);  // counting frequency of each element in nums\n\tfor(int i = 1; i <= 2*MAXN; ++i) freq[i] += freq[i - 1];   // building prefix sum array of freq. Now freq[i] will hold the frequency of numbers less than or equal to i\n\t// Each num will be assumed in the denominator as floor(nums[i] / num) and \n\t// using freq array, we can calculate the number of terms contributing 1, 2, 3... to the sum each.\n\tfor(auto num : nums) { \n\t\tlong l = num, r = 2 * num - 1, divResult = 1;\n\t\twhile(l <= mx) {                \n\t\t\tsum = (sum + divResult * (freq[r] - freq[l - 1])) % MOD;\n\t\t\tl += num, r += num;\n\t\t\t++divResult;\n\t\t}\n\t}\n\treturn sum;\n}\n```\n\n---\n---\n\n\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---
['C']