Make Sum Divisible by P

MediumArrays & Hashingprefix sum

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given an array of positive integers nums and an integer p, remove the **shortest** contiguous subarray (possibly empty) so that the sum of the remaining elements is divisible by p. You are not allowed to remove the entire array. Return the length of the removed subarray, 0 if the total is already divisible by p, or -1 if no allowed removal works. Aim for O(n) time.

Examples

Input: nums = [3,1,4,2], p = 6
Output: 1
The sum is 10, remainder 4. Removing [4] leaves 6, which is divisible by 6.
Input: nums = [6,3,5,2], p = 9
Output: 2
Removing [5,2] leaves 9.
Input: nums = [1,2,3], p = 7
Output: -1
Removing anything short of the whole array cannot make the remaining sum a multiple of 7.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More prefix sum problems