Sum of Floored Pairs - Practice Coding Problems

Sum of Floored Pairs - Problem

Given an integer array nums, return the sum of floor(nums[i] / nums[j]) for all pairs of indices 0 <= i, j < nums.length in the array.

Since the answer may be too large, return it modulo 10^9 + 7.

The floor() function returns the integer part of the division.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,5,1]

› Output: 12

💡 Note: All pairs: floor(2/2)=1, floor(2/5)=0, floor(2/1)=2, floor(5/2)=2, floor(5/5)=1, floor(5/1)=5, floor(1/2)=0, floor(1/5)=0, floor(1/1)=1. Sum = 1+0+2+2+1+5+0+0+1 = 12

Example 2 — Small Array

$ Input: nums = [7,7,7,7,7,7,7]

› Output: 49

💡 Note: All elements are 7, so floor(7/7)=1 for all 49 pairs (7×7), giving sum = 49

Example 3 — Edge Case

$ Input: nums = [1,1]

› Output: 2

💡 Note: Two pairs: floor(1/1)=1, floor(1/1)=1. Sum = 1+1 = 2

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of integers: [2,5,1]

Process

Calculate floor(nums[i]/nums[j]) for all pairs (i,j)

Output

Sum all floor division results

Key Takeaway

🎯 Key Insight: Instead of computing each pair individually, group by frequency or use binary search to handle ranges of similar quotients efficiently

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to avoid computing every individual pair by using frequency counting or binary search optimization. The brute force O(n²) approach works but can be optimized using frequency maps for arrays with duplicates or binary search for sorted ranges. Best approach depends on data characteristics: frequency counting for many duplicates, binary search for unique values. Time: O(n²) to O(n² log n), Space: O(1) to O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n²)	O(1)	Calculate floor(nums[i] / nums[j]) for every pair (i,j) and sum them up
Binary Search with Sorted Array	O(n² log n)	O(1)	Sort array and use binary search to count quotient ranges efficiently
Frequency Count Optimization	O(k²)	O(k)	Count frequency of each number and calculate contributions efficiently

Brute Force - Check All Pairs — Algorithm Steps

Iterate through each index i
For each i, iterate through each index j
Calculate floor(nums[i] / nums[j]) and add to sum
Return sum modulo 10^9 + 7

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Array with indices marked

Calculate

Compute floor division for each pair

Sum

Add all results together

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    const int MOD = 1000000007;
    long long total = 0;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < numsSize; j++) {
            total = (total + nums[i] / nums[j]) % MOD;
        }
    }
    
    return total;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int count = 0;
    char* token = strtok(line, "[,]");
    
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[count++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops iterate through all n² pairs

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses a few variables for sum and loop counters

✓ Linear Space

23.5K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler