Stretch Summing to a Multiple
MediumArrays & Hashing
Problem
A bakery packs cookies in boxes of k. The array nums lists how many cookies came out of each consecutive oven run (negative values are corrections). The manager asks whether there is a stretch of at least two consecutive runs whose combined cookies fill whole boxes with none left over.
Return true if some contiguous subarray of length at least 2 has a sum that is a multiple of k (0 counts as a multiple), and false otherwise.
Example 1
- Input:
- nums = [5, 2, 4, 1], k = 6
- Output:
- true
[2, 4] sums to 6.
Example 2
- Input:
- nums = [1, 2, 4], k = 5
- Output:
- false
The stretches of length ≥ 2 sum to 3, 6 and 7.
Example 3
- Input:
- nums = [6, 1], k = 6
- Output:
- false
6 alone is a multiple, but a stretch needs at least two runs, and 6 + 1 = 7.
Constraints
- 1 ≤ nums.length ≤ 10^5
- -10^9 ≤ nums[i] ≤ 10^9
- 1 ≤ k ≤ 2^31 - 1
Hint
Show the first hint
When is the sum of nums[i..j] a multiple of k, in terms of prefix sums?
Walkthrough
How to approach it
01Clarify before coding
- Does a single element count? No, the stretch needs at least two elements.
- Is 0 a multiple of k? Yes.
- Can values be negative? Yes, so normalise remainders.
02Brute force
Try every pair (i, j) with j ≥ i + 1, maintaining a running sum from i.
Cost: O(n²) time: 5·10^9 steps for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.