94. Trim to Divisible
A warehouse has a row of crates, and nums[i] is the weight of crate i. A shipping rule says the total weight loaded onto the truck must be divisible by p. To satisfy it, the manager may take away one contiguous block of crates (the block may also be empty, meaning nothing is removed) and load the rest.
Return the length of the shortest block that has to be removed so that the remaining crates have a total weight divisible by p. At least one crate must stay in the row, so removing everything is not allowed. If there is no valid way, return -1. If the whole row already satisfies the rule, the answer is 0.
Example 1
- Input:
- nums = [3,1,4,1,5], p = 5
- Output:
- 1
- Explanation:
The total is 14, which leaves remainder 4 modulo 5; removing the single crate of weight 4 leaves 10, so the answer is 1.
Example 2
- Input:
- nums = [6,3,5,2], p = 9
- Output:
- 2
- Explanation:
The total 16 leaves remainder 7 modulo 9; the shortest block with that remainder is [5, 2], so the answer is 2.
Constraints
1 ≤ nums.length ≤ 5 * 105
0 ≤ nums[i] ≤ 109
1 ≤ p ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n)
- Space
- O(min(n, p))