Shortest Trim for a Divisible Total
MediumArrays & Hashing
Problem
A shipment of n consecutive pallets must be split evenly across p trucks: the total number of boxes has to be a multiple of p. If it is not, the dispatcher may hold back one contiguous block of pallets (possibly empty) to fix the total, but cannot hold back all of them.
Given the positive box counts nums and p, return the length of the shortest contiguous block to remove so that the sum of the remaining elements is divisible by p, or -1 if that is impossible.
Example 1
- Input:
- nums = [4, 1, 2, 6], p = 6
- Output:
- 1
The total is 13, one more than 12. Removing [1] leaves 12.
Example 2
- Input:
- nums = [4, 4, 4, 6], p = 10
- Output:
- 2
Total 18 leaves remainder 8; no single pallet has 8 mod 10, but removing [4, 4] leaves 10.
Example 3
- Input:
- nums = [2, 2, 2], p = 7
- Output:
- -1
Only removing everything (6) would work, which is not allowed.
Constraints
- 1 ≤ nums.length ≤ 10^5
- 1 ≤ nums[i] ≤ 10^9
- 1 ≤ p ≤ 10^9
Hint
Show the first hint
Let r = total mod p. If r = 0 nothing needs removing. Otherwise, what must the removed block's sum be, mod p?
Walkthrough
How to approach it
01Clarify before coding
- Is removing nothing allowed? Yes: if the total is already divisible, return 0.
- Can I remove the whole array? No; if that is the only option, return -1.
- Can sums overflow? Totals reach 10^14; reduce mod p as you go (safe in Python and in JS doubles).
02Brute force
Try every block (i, j), compute the remaining sum with prefix sums and keep the shortest valid block.
Cost: O(n²) time: 5·10^9 checks 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.