We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Floored Pairs

Number: 1326

Difficulty: Hard

Paid? No

Companies: Rakuten

Problem Description

Given an integer array nums, calculate the sum of floor(nums[i] / nums[j]) for every possible pair (i, j), where floor() returns the integer part of the division. Since the answer may be very large, return it modulo 10^9 + 7.

Key Insights

  • Direct double iteration over pairs is too slow for large arrays, so we need to use mathematical observations.
  • By computing the frequency of each number and a prefix sum array, we can efficiently count the number of elements within any range.
  • For every candidate divisor d that appears in the array, iterate over its multiples. For each multiple, numbers in the range [multiple, multiple + d - 1] will have floor(value/d) equal to the quotient.
  • Sum the contributions of pairs by multiplying the frequency of d by the quotient and the count of numbers in the current range.

Space and Time Complexity

Time Complexity: O(max(nums) * log(max(nums))) due to iterating through potential divisors and their multiples. Space Complexity: O(max(nums)) for the frequency and prefix arrays.

Solution

We first calculate the frequency of each number in nums and build a prefix sum array to quickly determine how many numbers fall inside a given range. For each divisor d (from 1 to max(nums)) that appears in the array, iterate over its multiples (j = d, 2d, 3d, ...). For each multiple, the numbers in the interval [j, min(j+d-1, maxValue)] all have floor(x/d) equal to j/d. Multiply frequency[d] by (j/d) and by the count of numbers in that range (obtained from the prefix sums). Sum all such contributions and return the result modulo 10^9+7.

Code Solutions

# Python solution for Sum of Floored Pairs

MOD = 10**9 + 7

def sum_of_floored_pairs(nums):
    # max_val is the largest number in nums
    max_val = max(nums)
    # Build frequency array up to max_val
    freq = [0] * (max_val + 1)
    for num in nums:
        freq[num] += 1

    # Build prefix sum array to quickly query counts in any range
    prefix = [0] * (max_val + 1)
    prefix[0] = freq[0]
    for i in range(1, max_val + 1):
        prefix[i] = prefix[i - 1] + freq[i]

    # Helper function to get count of numbers in range [low, high]
    def get_count(low, high):
        if low > high:
            return 0
        return prefix[high] - (prefix[low - 1] if low > 0 else 0)

    result = 0
    # Iterate through each possible divisor d
    for d in range(1, max_val + 1):
        if freq[d] == 0:
            continue
        # Iterate over multiples of d
        multiple = d
        while multiple <= max_val:
            # Determine the range where floor(x / d) equals multiple // d
            low = multiple
            high = min(multiple + d - 1, max_val)
            count_in_range = get_count(low, high)
            result = (result + freq[d] * (multiple // d) * count_in_range) % MOD
            multiple += d
    return result

# Example usage:
nums = [2, 5, 9]
print(sum_of_floored_pairs(nums))  # Expected output: 10
← Back to All Questions