Show problems as
Classic problem #1590MediumArrayHash TablePrefix Sum

Make Sum Divisible by P

Real-world version: Shortest Run to Pull From the Load
Tracked in this browser only
Read Make Sum Divisible by P on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A freight car is loaded with pallets in a single row, and nums[i] is the weight of the pallet in position i. The yard will only release the car when the total weight on board is a multiple of p.

You may pull out one unbroken run of pallets, and only one. You may also pull out nothing at all. You may not pull out every pallet: at least one pallet has to stay on board.

Return the length of the shortest run you can pull out so that the weight left on board is a multiple of p. If no choice of run works, return -1. Pulling out nothing counts as a run of length 0.

Examples

Example 1

Input
nums = [9, 2, 6, 4, 5], p = 11
Output
1

The load weighs 26, which is not a multiple of 11. Pulling out the single pallet in position 3, weight 4, leaves 22 on board, and 22 is 11 twice over.

Example 2

Input
nums = [5, 5, 5], p = 7
Output
-1

The load weighs 15. The runs available are of weight 5, 5, 5, 10 and 10, and none of them leaves a multiple of 7 behind. Pulling out all three pallets would leave 0, which is a multiple of 7, but the car may not be emptied.

Example 3

Input
nums = [1, 2, 3], p = 1
Output
0

Every whole number is a multiple of 1, so the load already qualifies and nothing has to come off.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= p <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_subarray(nums: list[int], p: int) -> int:
Java
public int minSubarray(int[] nums, int p)

More on the same topics