1862. Sum of Floored Pairs

HardArrayMathBinary SearchPrefix Sum
Leetcode Link

Problem Description

The task is to find the sum of the integer parts of the fractions formed by dividing each element in the given integer array nums by every other element in the same array. This means for each pair of indices (i, j) in the array, we're calculating floor(nums[i] / nums[j]), where floor() is a mathematical function that returns the largest integer less than or equal to a given number (the integer part of a division). All possible pairwise divisions are included. The result could potentially be very large, so we return the final sum modulo 10^9 + 7 to keep the number within the bounds of typical 32-bit integer representation and to manage big numbers in a reasonable way, as often required in computational problems.

Intuition

To solve this problem, we employ several algorithmic strategies to make the calculations efficient. Since we are dealing with all possible pairs, a naรฏve solution could take up too much time, especially for large arrays. Here are some observations and steps to approach the solution more efficiently:

  1. Counting Occurrences: We first count how many times each number appears in the array nums. This is important because the same division will occur as many times as the number appears. We keep these counts in a dictionary or array, referred to as cnt.

  2. Prefix Sum Array: Next, we construct a prefix sum array s that keeps a running sum of counts of numbers up to each index. s[i] contains the total number of array numbers less than or equal to i. This step will greatly accelerate finding the sum of counts between any two number ranges since it'll be a simple subtraction, s[j] - s[i - 1].

  3. Enumerating Divisors and Quotients: Now, instead of looping over every pair, we iterate over all possible divisors y that appear in nums and then for each y, over all possible quotients d. For each quotient, we calculate how many numerators give this specific quotient when divided by y using the prefix sum array. This is the number of pairs (i, j) where nums[i] / nums[j] yields quotient d.

  4. Calculating the Sum: For each d and y, we can find the sum of floor(nums[i] / nums[j]) by taking the count of such numerators from the prefix sum array, multiplying it with count of y and quotient d. Finally, we accumulate these into the ans variable.

  5. Modulo Arithmetic: We have to frequently follow modulo to avoid integer overflow issues. Each intermediate sum is taken modulo 10^9 + 7 to maintain a manageable number size.

By implementing these steps, we optimize the brute force enumeration approach into an efficient calculation involving counting, prefix sums, and careful iteration to avoid unnecessary recalculations, leading to a manageable time complexity for large input sizes.

Learn more about Math, Binary Search and Prefix Sum patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Solution Approach

The implementation of the given solution follows a structured approach that utilizes algorithms, data structures, and patterns to efficiently compute the required sum. Here's a step-by-step explanation of how the solution approach mentioned above is implemented:

  1. Initialize Data Structures:

    • A dictionary or counter, named cnt, to store counts of each unique number in nums.
    • A list s of size mx + 1, where mx is the maximum number found in nums, to store the prefix sum of counts.

  2. Build Counters and Prefix Sum:

    • Use the Counter class from the collections module to count occurrences of numbers in nums: cnt = Counter(nums).
    • Create the prefix sum array. The element s[i] is computed by adding cnt[i] to the prefix sum up to i - 1: s[i] = s[i - 1] + cnt[i].

  3. Enumerate Denominators:

    • Loop through possible divisors y ranging from 1 to mx. Here y will be the denominator when calculating floor(nums[i] / nums[j]).
    • For each y, we only continue if y was present in nums (if cnt[y]:), to avoid unnecessary computations.

  4. Enumerate Quotients:

    • For the chosen y, iterate through possible quotients d starting from 1, incrementing d till d * y exceeds mx.
    • During each iteration, calculate the count of numerators that would yield the quotient d when divided by y. This is done by subtracting the prefix sum up to d * y - 1 from the prefix sum up to min(mx, d * y + y - 1).
    • The result s[min(mx, d * y + y - 1)] - s[d * y - 1] gives us the number of numerators in the specified range.

  5. Compute Contribution to Answer:

    • Multiply the count of numerators by cnt[y] and the quotient d to find the total contribution of that quotient with the denominator y to the final answer.
    • Add this value to ans, ensuring at each step to apply modulo 10^9 + 7 to keep the value within bounds: ans += cnt[y] * d * (s[min(mx, d * y + y - 1)] - s[d * y - 1]) % mod.

  6. Return Result:

    • After completing the enumeration of y and d, return the accumulated ans.

Each step incorporates careful use of algorithms (use of counting and prefix sums) and data structures (arrays for prefix sums, counters for occurrences) alongside modular arithmetic to not only bring down the complexity but also manage the large numbers. This approach provides a significant performance advancement compared to the brute force method that would have had a prohibitive time complexity for large inputs.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose our input array nums is [1, 2, 3, 4, 6]. We want to find the sum modulo 10^9 + 7 of the integer parts of the fractions formed by dividing each number in nums by every other number in the same array.

  1. Initialize Data Structures:

    • Let cnt be our dictionary which will store occurrences of each number. cnt = {1:1, 2:1, 3:1, 4:1, 6:1}
    • The list s will store the prefix sum of counts. Since our mx is 6, s = [0, 0, 0, 0, 0, 0, 0] initially.

  2. Build Counters and Prefix Sum:

    • cnt will be populated straight from our array: cnt = Counter([1, 2, 3, 4, 6]).
    • To build the prefix sum array, we update s:
      • s[1] = 1, s[2] = s[1] + 1, s[3] = s[2] + 1, and so on until s[6] = s[5] + 1.
    • The complete s becomes [0, 1, 2, 3, 4, 4, 5].

  3. Enumerate Denominators:

    • We loop through possible divisors y from 1 to 6.

  4. Enumerate Quotients:

    • For each y, iterate through possible quotients d. For example, for y = 2:
    • Quotient d = 1, numerator range is [2, 3]. s[3] - s[1] = 2 numerators.
    • Quotient d = 2, numerator range is [4, 5]. s[5] - s[3] = 1 numerator.
    • And so on until d * y > mx.

  5. Compute Contribution to Answer:

    • For each d, calculate its contribution:
      • d = 1: cnt[2] * 1 * (s[3] - s[1]) % mod = 1 * 1 * (2 - 1) % mod = 1
      • d = 2: cnt[2] * 2 * (s[5] - s[3]) % mod = 1 * 2 * (1 - 0) % mod = 2
    • Repeat above steps for each divisor y and accumulate the answer into ans.

  6. Return Result:

    • After iterating over all y and d pairs, the ans might look something like this: ans = 1 + 2 + (other contributions calculated using the same steps).
    • Finally, ans % mod is returned as the result.

This walkthrough has demonstrated how each step in the solution works together. By avoiding the brute force enumeration for every pair and applying more efficient arithmetic and data structures, the overall computation becomes significantly faster, making it viable even for larger arrays.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def sum_of_floored_pairs(self, nums):
5        MODULO = 10 ** 9 + 7  # Constant for modulo operation to prevent large integer values
6        num_counts = Counter(nums)  # Count the frequency of each number in nums
7        max_num = max(nums)  # Find the maximum number in the list
8        prefix_sum = [0] * (max_num + 1)  # Create a list for prefix sum of counts
9
10        # Calculate the prefix sum for counts of each number
11        for i in range(1, max_num + 1):
12            prefix_sum[i] = prefix_sum[i - 1] + num_counts[i]
13      
14        answer = 0  # This will store the final answer
15
16        # Iterate over each unique number to calculate contributions
17        for divisor in range(1, max_num + 1):
18            if num_counts[divisor]:
19                multiple = 1
20                # For each divisor, calculate floor pairs for its multiples
21                while multiple * divisor <= max_num:
22                    # Increment answer by number of pairs times current multiple
23                    range_sum = prefix_sum[min(max_num, multiple * divisor + divisor - 1)] - prefix_sum[multiple * divisor - 1]
24                    answer += num_counts[divisor] * multiple * range_sum
25                    answer %= MODULO  # Take mod to avoid large numbers
26                    multiple += 1  # Increment the multiple for the next iteration
27
28        return answer
29
1class Solution {
2    public int sumOfFlooredPairs(int[] nums) {
3        final int MOD = (int) 1e9 + 7; // Define the mod for the final answer
4        int maxElement = 0;
5
6        // Find the maximum element in the array
7        for (int num : nums) {
8            maxElement = Math.max(maxElement, num);
9        }
10
11        // Create a frequency array
12        int[] frequency = new int[maxElement + 1];
13
14        // Create an array to hold the prefix sum of the frequency array
15        int[] prefixSum = new int[maxElement + 1];
16
17        // Count the frequency of each number in the array
18        for (int num : nums) {
19            ++frequency[num];
20        }
21
22        // Calculate the prefix sum of the frequency array
23        for (int i = 1; i <= maxElement; ++i) {
24            prefixSum[i] = prefixSum[i - 1] + frequency[i];
25        }
26
27        long answer = 0; // This will store the final result
28
29        // Iterate through all the unique elements in nums (as per the frequency)
30        for (int num = 1; num <= maxElement; ++num) {
31            if (frequency[num] > 0) {
32                // For each unique element, find the sum of floored pairs
33                for (int divisor = 1; divisor * num <= maxElement; ++divisor) {
34                    // Add the contribution of the current divisor to the total sum
35                    answer += (long) frequency[num] * divisor * (prefixSum[Math.min(maxElement, divisor * num + num - 1)] - prefixSum[divisor * num - 1]);
36                    answer %= MOD; // Modulo operation to keep the sum within bounds
37                }
38            }
39        }
40
41        // Return the answer cast to an integer
42        return (int) answer;
43    }
44}
45
1class Solution {
2public:
3    int sumOfFlooredPairs(vector<int>& nums) {
4        const int MOD = 1e9 + 7; // Use a constant for the modulo value
5        int maxNum = *max_element(nums.begin(), nums.end()); // Find the max number in nums
6        vector<int> count(maxNum + 1, 0); // Counts for each number up to maxNum
7        vector<int> prefixSum(maxNum + 1, 0); // Prefix sums of the counts
8        // Populate the count array
9        for (int num : nums) {
10            ++count[num];
11        }
12        // Calculate the prefix sum array
13        for (int i = 1; i <= maxNum; ++i) {
14            prefixSum[i] = prefixSum[i - 1] + count[i];
15        }
16        long long answer = 0; // Accumulate the final answer
17        // Iterate over all numbers in count array
18        for (int y = 1; y <= maxNum; ++y) {
19            if (count[y]) { // If this number appears in nums
20                // For each multiple of the number y, calculate contributions
21                for (int multiplier = 1; multiplier * y <= maxNum; ++multiplier) {
22                    int nextBound = min(maxNum, multiplier * y + y - 1);
23                    answer += static_cast<long long>(count[y]) * multiplier *
24                              (prefixSum[nextBound] - prefixSum[multiplier * y - 1]);
25                    answer %= MOD; // Ensure we are within the modulo value
26                }
27            }
28        }
29        return answer; // Return the computed result
30    }
31};
32
1function sumOfFlooredPairs(nums: number[]): number {
2    // Find the maximum value in the array to define the range of prefixes
3    const maxNum = Math.max(...nums);
4  
5    // Initialize a counter array to store the frequency of each number up to the maximum
6    const frequency: number[] = Array(maxNum + 1).fill(0);
7  
8    // Initialize a prefix sum array to store the running sum of frequencies
9    const prefixSum: number[] = Array(maxNum + 1).fill(0);
10  
11    // Fill the frequency array with the frequency of each number in 'nums'
12    for (const num of nums) {
13        ++frequency[num];
14    }
15  
16    // Compute the prefix sums of frequencies
17    for (let i = 1; i <= maxNum; ++i) {
18        prefixSum[i] = prefixSum[i - 1] + frequency[i];
19    }
20  
21    // Initialize the answer variable to store the final result
22    let answer = 0;
23    const modulo = 1e9 + 7; // Modulus to prevent overflow
24  
25    // Traverse through the range of numbers
26    for (let y = 1; y <= maxNum; ++y) {
27        if (frequency[y]) { // Only proceed if the current number has a non-zero frequency
28            for (let d = 1; d * y <= maxNum; ++d) {
29                answer += frequency[y] * d * (prefixSum[Math.min((d + 1) * y - 1, maxNum)] - prefixSum[d * y - 1]);
30                answer %= modulo;
31            }
32        }
33    }
34  
35    // Return the final answer
36    return answer;
37}
38
Not Sure What to Study? Take the 2-min Quiz๏ผš

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Time and Space Complexity

Time Complexity

The time complexity of the function sumOfFlooredPairs is largely determined by the nested loop structure where the outer loop runs for numbers from 1 to the maximum number mx in the array nums, and the inner loop runs while d * y is less than or equal to mx. For each outer loop iteration, the inner loop runs approximately mx / y times. Summing this over all y from 1 to mx gives the geometric series sum which is proportional to mx * log(mx). Thus, the total time complexity is O(M * log(M)), where M is the maximum value in the array nums.

Space Complexity

The space complexity is determined by the additional memory used by the algorithm which includes the cnt Counter and the prefix sum array s. Both of these data structures have a size that is dependent on the maximum value mx in the array nums, not the length of the nums array itself. Since s is an array of length mx + 1, the space complexity is O(M). The cnt Counter also does not exceed O(M) in size, so the overall space complexity remains O(M).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ