All problems

Make the Total Divisible by P

Medium · prefix sum

You are given a list of positive integers nums and a positive integer p.

You may remove one run of numbers: a block of neighbouring numbers, taken out together. The run can also be empty, which means removing nothing. You are not allowed to remove every number, so at least one number must stay. After the removal, the total of the numbers that remain must be divisible by p.

Return the length of the shortest run you can remove to achieve this. If the total is already divisible by p, the answer is 0. If no allowed removal works, return -1.

Examples

Example 1

Input: nums = [6, 3, 5, 2], p = 9

Output: 2

The total is 16. Removing the run [5, 2], which adds up to 7, leaves 6 + 3 = 9, which is divisible by 9. No single number works.

Example 2

Input: nums = [4, 6, 8], p = 2

Output: 0

The total is 18, already divisible by 2, so nothing needs to be removed.

Example 3

Input: nums = [1, 2, 3], p = 7

Output: -1

The total is 6. The only run whose removal would leave a multiple of 7 is the whole list, and that is not allowed.

Constraints