Factor Frequency Prefix Sum w/Num Frequency Product | Commented and Explained | O(N) T/S
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem description is deceptively simple and at first a brute force even seems a l
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem description is deceptively simple and at first a brute force even seems a likely and doable option, for which I got 19/51 and then 25/51 with first Time and then Memory limit expired. From this, it becomes more obvious that we need a more clever solution. \n\nThe first part in any good brute force to get that far was the reduction in time afforded by considering only unique values in nums and using the frequency of those values. \n\nThe second trick was when I considered the contribution of a specific value to a specific total sum. Take 9 and 2. 9 / 2 in floor form gives 4. This can be seen as the statement that there are 4 factors of 2 in 9 (2, 4, 6, 8). This is the key to the second speed up. \n\nIf we keep a number range from 0 to the maximum of nums, then we can account for this contribution exactly. \n\n- For each unique factor in nums \n    - for each next factor of this unique factor up to max nums \n        - store the frequency of this factor at a point next factor in our number range \n\n- Then, get the prefix sum of the factor frequencies as a list \n- Then, for each actual num in our num frequencies, multiply the prefix sum of the factor frequencies by the frequency of that num. This then gets the other half of the question. \n\nTo simplify, first find out how much and how many items utilize each factor in nums. Then, find out for each of those utilizations what their summed contribution is. Then, sum only the given unique factor contributions present by the frequency of that factor. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIntuitition describes much of the approach, but for completeness, steps outlined here. \n\nGet the frequency of nums \nSet up modulo value as needed \nGet the maximum key in frequency of nums \nSet up a factor frequencies of 0 in range of max key inclusive \n\nFor num and frequency in frequency of nums \n- for factor in range num, max key + 1, num \n    - factor frequencies at factor += frequency \n\nGet the prefix sum of factor frequencies \n\nreturn the sum of the product of the prefix sum of factor frequencies for each factor in num frequency with the frequency of that factor  \n\n# Complexity\n- Time complexity : O(N) \n    - O(N) to get num frequency \n    - O(n) to get unique max value \n    - O(n * floor(max value / avg other nums)) \n    - O(max value) to get prefix sums \n    - O(n) to get final value  \n    - At worst one might think O(N) == O(n) == O(max value) \n    - However, when that occurs avg of other nums ~ N \n    - Due to this, we can see that the floor mechanism limits \n    - Worst would be when n ~ N/2 and n is composed of all values up to N/2 - 1 and N \n    - This would give a run time of N/2 * 2 for the loop and shows the value of the floor limit on the run time for the inner loop \n    - Thus we can say at worst O(N) \n\n- Space complexity : O(N) \n    - As above, at worst is O(N)  \n\n# Code\n```\nclass Solution:\n    def sumOfFlooredPairs(self, nums: List[int]) -> int :\n        # uncomment print statements to see in test cases \n        # floor nums[i] / nums[j]\n        # if nums[i] occurrs multiple times, doing multiple work \n        # frequency is first reduction \n        num_frequency = collections.Counter(nums)\n        mod = 10**9 + 7 \n        # second reduction involves consideration of factorization processes \n        # for each value in nums, that number will have a number of contributions based on its frequency for its value \n        # in relation to all other values. For example, 9 / 2 causes 2 to contribute 4 due to the presence of 9\n        # this can be seen as the number of factors of 2 that fit within the value of 9. Due to this, we want to find \n        # first the largest value of our num frequency (don\'t search nums! Already did that once to set up num frequency) \n        # then we want to find the frequencies related to the factors of a value that fit within range up to that max value \n        # this will give us our second reduction, since we can now do loops limited to only unique nums in num frequency \n        # as the outer loop and do inner loops over only the factor range for each value, which processes in logarithmic\n        # time rather than linear time due to size of steps utilized in advancing towards a set max value \n        max_key = max(num_frequency.keys())\n        # then, for each factor in range of a num to the max key plus 1 so that the max value is included \n        # we will record the frequency that a given factor for any num of nums is found in range and increment \n        # by the frequency of the associated base num, as that will denote the contribution frequency times it makes \n        # towards the total summation value \n        factor_frequencies = [0] * (max_key + 1) \n        # loop over num frequency items \n        for num, frequency in num_frequency.items() : \n            # print(f\'Considering number {num} with frequency {frequency}\')\n            # factor values in range of num to max key + 1 in steps of num \n            # represents reduction in time by use of multiples of num that are found in floor pairings \n            for factor in range(num, max_key + 1, num) : \n                # print(f\'Considering factor value {factor} and updating factor frequencies current : {factor_frequencies}\')\n                # for which you will have at least frequency occurrences of this value for that partner \n                factor_frequencies[factor] += frequency\n                # print(f\'New factor_frequencies is {factor_frequencies}\\n\')\n        # print(f\'Total factor_frequencies are {factor_frequencies}\')\n        # this is the prefix sum of the factors of num frequencies in range of max, accounting for \n        # the possible multiple divisions of certain nums by certain other values (i.e. 9 / 2 -> 4)\n        prefix_sum_of_factor_frequencies = list(accumulate(factor_frequencies))\n        # print(f\'Prefix sum of factor frequencies are {prefix_sum_of_factor_frequencies}\')\n        # return the sum of the prefix sum of factor frequencies for each num actually in num frequency multiplied \n        # by the frequency of that num. This is because the prefix sum accounts for the number of times it is utilized by others, and now we count by self \n        return sum(prefix_sum_of_factor_frequencies[num] * frequency for num, frequency in num_frequency.items()) % mod \n```
['Python3']