💥💥 C# | 100% beats runtime AND memory [EXPLAINED]
\n# Intuition\nThe goal is to find the sum of floor divisions for all possible pairs in the array, where one number divides the other. Directly computing this f
\n# Intuition\nThe goal is to find the sum of floor divisions for all possible pairs in the array, where one number divides the other. Directly computing this for every pair would be too slow, so we use a more efficient approach. By leveraging frequency counts and prefix sums, we avoid redundant calculations and speed up the process.\n\n\n# Approach\nCount Frequencies: First, count how many times each number appears in the array. This helps us quickly know how many times a number can contribute to the result.\n\n\nPrefix Sum Array: Build a prefix sum array from these counts to quickly compute how many numbers fall within certain ranges.\n\n\nCalculate Contributions: For each number, determine how many multiples of it exist and compute their contributions using the frequency and prefix sum arrays.\n\n\nSum Up Results: Accumulate these contributions, making sure to handle large numbers with modulo 10(and factor of 9) +7.\n\n\n# Complexity\n- Time complexity:\nO(n + maxVal log maxVal): Efficient due to counting and prefix sums.\n\n\n- Space complexity:\nO(maxVal): Space for frequency and prefix sums, manageable given constraints.\n\n\n# Code\n```csharp []\npublic class Solution {\n    private const int MOD = 1000000007;\n\n    public int SumOfFlooredPairs(int[] nums) {\n        int maxVal = 100000;\n        int[] freq = new int[maxVal + 1];\n        \n        // Count the frequency of each number in the input array\n        foreach (int num in nums) {\n            freq[num]++;\n        }\n        \n        // Build the prefix sum of the frequency array\n        int[] prefixSum = new int[maxVal + 1];\n        for (int i = 1; i <= maxVal; i++) {\n            prefixSum[i] = prefixSum[i - 1] + freq[i];\n        }\n        \n        long result = 0;\n        \n        // For each number i, calculate its contribution to the result\n        for (int i = 1; i <= maxVal; i++) {\n            if (freq[i] == 0) continue;  // Skip numbers that don\'t appear in the input\n\n            // For each multiple of i, sum the floor divisions\n            for (int multiple = i; multiple <= maxVal; multiple += i) {\n                int low = multiple;\n                int high = Math.Min(maxVal, multiple + i - 1);\n                int countInRange = prefixSum[high] - prefixSum[low - 1];\n\n                result = (result + (long)freq[i] * countInRange * (multiple / i)) % MOD;\n            }\n        }\n        \n        return (int)result;\n    }\n}\n\n```
['C#']