Even Distribution of Integers — Problem Statement & Solution Guide
Problem Description
You are given an array of integers crates representing the number of packets in each crate. Determine the maximum number of packets each crate can be filled with if the total packets are distributed evenly, and find the number of crates that will have remaining packets.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Even Distribution of Integers"
WHY DOES IT MATTER?
This pattern is essential for any system requiring fair resource allocation, load balancing, or data sharding. It tests the candidate's understanding of integer arithmetic, edge cases (division by zero, large numbers), and the ability to derive a constant-time solution from a seemingly complex distribution problem.
OPTIMIZATION CHALLENGE
The key insight is recognizing that you do not need to simulate the distribution process (which would be $O(N)$ or $O(K)$). Instead, you can compute the result in $O(1)$ time using the properties of the modulo operator and integer division. The challenge is correctly interpreting 'number of crates with remaining packets'—it is simply the remainder value if each crate gets at most one extra packet.
REAL-WORLD CONNECTION
This is directly analogous to DNS round-robin load balancing or database sharding. When a database is sharded across $K$ nodes, the hash of a key modulo $K$ determines the node. The 'remainder' represents the uneven distribution of keys, which is critical for understanding hotspots and data skew in distributed systems.
In interviews, always clarify the definition of 'remaining packets.' Does it mean crates that have *any* leftover, or crates that have *uneven* distribution? Usually, it implies the remainder $r$ represents the count of crates that receive $q+1$ packets, while $K-r$ crates receive $q$ packets. State this assumption clearly before coding.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
The problem 'Even Distribution of Integers' is fundamentally a modular arithmetic and aggregation problem. The core theoretical underpinning lies in the division algorithm, which states that for any integers $a$ (dividend) and $b$ (divisor, $b > 0$), there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = bq + r$ and $0 \le r < b$. In this context, the total number of packets is the dividend, and the number of crates is the divisor. The maximum number of packets each crate can be filled with evenly is the quotient $q = \lfloor \text{total} / n \rfloor$, and the number of crates with remaining packets is determined by the remainder $r = \text{total} \% n$. If $r > 0$, exactly $r$ crates will have one extra packet (or the remainder distributed among them, depending on specific distribution rules, but the count of 'affected' crates is tied to the remainder).
Interview Questions on This Problem
Q1At a fintech platform like Stripe, we need to distribute a large batch of transaction fees evenly across a cluster of settlement servers. If the total fee amount is $10^9$ and there are 1,000 servers, how do you calculate the base allocation and the number of servers that will handle the residual amount? Why is using floating-point division dangerous here?
Use integer division to find the base allocation: $10^9 // 1000 = 1,000,000$. The residual is $10^9 \% 1000 = 0$. If the total were $1,000,001$, the residual would be 1, meaning 1 server gets an extra unit. Floating-point division is dangerous because of precision loss with large integers (beyond $2^{53}$), which can lead to incorrect rounding and financial discrepancies. Always use integer arithmetic for exact distribution problems in financial systems.
Q2In a high-growth startup's load balancer, you have $N$ requests and $K$ worker nodes. You want to distribute requests as evenly as possible. What is the time complexity to compute the distribution if $N$ is extremely large (e.g., $10^{18}$) and $K$ is small? How would you handle the case where $K > N$?
The time complexity is $O(1)$ for the calculation itself, as it involves only summing (if not pre-summed) and two arithmetic operations. If $K > N$, the quotient is 0, and the remainder is $N$. This means $N$ nodes get 1 request, and $K-N$ nodes get 0. The key is to handle the edge case where the divisor is larger than the dividend, ensuring the logic for 'crates with remaining packets' correctly identifies that only $N$ crates are non-empty.
Q3A global product company like Amazon needs to distribute inventory units across warehouses. If the total units are 1,000,000 and there are 100 warehouses, but some warehouses have capacity constraints, how does the simple even distribution algorithm change? Does the basic quotient/remainder approach still apply directly?
The basic quotient/remainder approach provides the *ideal* even distribution. However, with capacity constraints, it becomes a constrained optimization problem (often solved via greedy or binary search). The simple algorithm fails if the calculated per-warehouse amount exceeds a warehouse's capacity. In an interview, you should first present the $O(1)$ ideal solution, then discuss how to adapt it by capping allocations and redistributing the overflow, which may increase complexity to $O(K \log K)$ or $O(K)$ depending on the sorting or heap usage.
Examples
Input
[14, 4]
Output
[3, 1, 1, 1]
Explanation: Step-by-step: Given an array of integers [14, 4], we first calculate the total number of packets (14) and the number of crates (4). We then calculate the base number of packets each crate can be filled with by doing integer division of the total number of packets by the number of crates (14 / 4 = 3). The remaining packets are then distributed evenly among the crates by doing integer division of the remaining packets by the number of crates (2 / 4 = 0). However, since we cannot distribute 0 packets to each crate, we distribute the remaining packets by doing integer division of the remaining packets by the number of crates (2 / 4 = 0), then we add 1 to each crate that has 0 packets, giving us [3, 1, 1, 1].
Input
[10, 5]
Output
[2, 0, 0, 0, 0]
Explanation: Step-by-step: Given an array of integers [10, 5], we first calculate the total number of packets (10) and the number of crates (5). We then calculate the base number of packets each crate can be filled with by doing integer division of the total number of packets by the number of crates (10 / 5 = 2). The remaining packets are then distributed evenly among the crates by doing integer division of the remaining packets by the number of crates (0 / 5 = 0). Since there are no remaining packets, we do not need to distribute any packets, giving us [2, 0, 0, 0, 0].
Constraints
- 1 <= crates.length <= 10^5
- 1 <= crates[i] <= 10^9
- The total number of packets will not exceed 10^12
Optimal Approach & Strategy
Calculate the sum of all packets in the array. Use integer division to determine the base allocation per crate and the modulo operator to find the remainder. The remainder directly indicates the number of crates that will have an extra packet.
Brute Force Approach
Iterate through each crate, subtracting packets one by one from the total until the total is zero, counting how many packets each crate receives. This is inefficient and prone to off-by-one errors for large inputs.
Verified Code Solutions
function solution(crates) {
let total = crates.reduce((a, b) => a + b, 0);
let base = Math.floor(total / crates.length);
let remaining = total % crates.length;
let result = crates.map(() => base);
for (let i = 0; i < remaining; i++) {
result[i]++;
}
return result;
}class Solution {
public:
int* solution(int* crates, int cratesSize) {
int total = 0;
for (int i = 0; i < cratesSize; i++) {
total += crates[i];
}
int base = total / cratesSize;
int remaining = total % cratesSize;
int* result = new int[cratesSize];
for (int i = 0; i < cratesSize; i++) {
result[i] = base;
}
for (int i = 0; i < remaining; i++) {
result[i]++;
}
return result;
}
};class Solution {
public int[] solution(int[] crates) {
int total = 0;
for (int crate : crates) {
total += crate;
}
int base = total / crates.length;
int remaining = total % crates.length;
int[] result = new int[crates.length];
for (int i = 0; i < crates.length; i++) {
result[i] = base;
}
for (int i = 0; i < remaining; i++) {
result[i]++;
}
return result;
}
}def solution(crates):
total = sum(crates)
base = total // len(crates)
remaining = total % len(crates)
result = [base] * len(crates)
for i in range(remaining):
result[i] += 1
return resultfunction solution(crates) {
let total = crates.reduce((a, b) => a + b, 0);
let base = Math.floor(total / crates.length);
let remaining = total % crates.length;
let result = crates.map(() => base);
for (let i = 0; i < remaining; i++) {
result[i]++;
}
return result;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.