Log inSign up
mediumLeetCodeNot Started

Make Sum Divisible by P

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.

A subarray is defined as a contiguous sequence of elements in the array.

Example 1 · Standard Remainder Removal:

Input: nums = [3, 1, 4, 2], p = 6
Output: 1
Explanation: Total sum = 10, 10 % 6 = 4. Removing [4] leaves [3, 1, 2] with sum = 6 (divisible by 6). Minimum length is 1.

Example 2 · Already Divisible:

Input: nums = [6, 3, 5, 2], p = 9
Output: 2
Explanation: Total sum = 16, 16 % 9 = 7. Removing [5, 2] of sum 7 leaves [6, 3] with sum = 9 (divisible by 9).

Example 3 · Cannot Remove Whole Array:

Input: nums = [1, 2, 3], p = 7
Output: -1
Explanation: Total sum = 6. There is no subarray of sum 6 that is not the entire array.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= p <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Prefix Sum modulo congruence
  • Hash Map for index lookup
  • Continuous Subarray Sum & Subarray Sum Equals K

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate modular subtraction: (cur - rem + p) % p to avoid negative remainders.
  • Understand why storing the LATEST index minimizes subarray length (contrast with Continuous Subarray Sum which maximizes length).
  • Handle the edge case where minLen == N (cannot remove whole array, must return -1).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • Compute targetRem = sum(nums) % p. If targetRem == 0, return 0.
  • At index j: targetPrev = (curMod - targetRem + p) % p.
  • If targetPrev exists in map, minLen = min(minLen, j - map[targetPrev]).
  • Always update map[curMod] = j (to keep the closest left bound and minimize length).

Connected Patterns:

Continuous Subarray SumSubarray Sum Equals KSubarray Sums Divisible by K

1. All Subarrays Evaluation (Brute Force)

Intuition

Calculate the total sum modulo p. Let rem = total % p. If rem == 0, return 0 immediately. Otherwise, test all pairs (i, j) with 0 <= i <= j < n. Compute subSum = sum(nums[i..j]). If subSum % p == rem and j - i + 1 < n, update minLen = min(minLen, j - i + 1).

When to apply: Use to verify the problem statement logic on small arrays before introducing modular arithmetic hash maps.

All Subarrays Removal (O(N^2) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Target remainder to remove is targetRem = 4
Visual state
Values and pointers at this exact step
pointers
S
3
1
4
2
0
↑ total
1
2
3
Variables at this step
totalSum
10
p
6
targetRem
4
minLen
null
Check / comparison
Total sum = 3 + 1 + 4 + 2 = 10. 10 % 6 = 4 != 0
Decision / next transition
Must remove a subarray whose sum % 6 == 4 to make remaining sum divisible by 6.
Why this step matters

Target remainder to remove is targetRem = 4.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int minSubarray(int[] nums, int p) {
4 long total = 0;
5 for (int x : nums) total += x;
6 int rem = (int)(total % p);
7 if (rem == 0) return 0;
8 int n = nums.length;
9 int minLen = n;
10 for (int i = 0; i < n; i++) {
11 long sum = 0;
12 for (int j = i; j < n; j++) {
13 sum += nums[j];
14 if (sum % p == rem && (j - i + 1) < n) {
15 minLen = Math.min(minLen, j - i + 1);
16 }
17 }
18 }
19 return minLen == n ? -1 : minLen;
20 }
21 }
22
23 public static void main(String[] args) {
24 Solution sol = new Solution();
25 int[] nums = {3, 1, 4, 2};
26 int p = 6;
27 System.out.println("Min Subarray Length: " + sol.minSubarray(nums, p));
28 }
29}

Time & Space Complexity

  • Time complexity: O(n^2) — Evaluating all O(n2) subarrays with running sum takes O(n2) time.
  • Space complexity: O(1) — O(1) auxiliary variables for pointers and sum trackers.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Prefix Modulo Array with Nested Check (Better)

Intuition

By computing prefix[i] = (prefix[i-1] + nums[i]) % p, any subarray sum modulo p from i to j can be found in O(1) time as (prefix[j] - prefix[i-1] + p) % p. A nested double loop checks all valid ranges in O(n2) without re-adding elements.

When to apply: Use to understand prefix sum modular transformations before introducing hash map lookups.

Prefix Remainder Array (O(N^2) Time, O(N) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Prefix remainder table precomputes modular sums
Visual state
Values and pointers at this exact step
pointers
S
0
3
4
2
4
0
↑ prefRem
1
2
3
4
Variables at this step
prefRems
[0,3,4,2,4]
targetRem
4
Check / comparison
Compute prefix remainders modulo 6: [0, 3, 4, 2, 4]
Decision / next transition
Target remainder to remove is totalRem = 4.
Why this step matters

Prefix remainder table precomputes modular sums.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int minSubarray(int[] nums, int p) {
4 int n = nums.length;
5 long[] prefix = new long[n + 1];
6 for (int i = 0; i < n; i++) {
7 prefix[i + 1] = prefix[i] + nums[i];
8 }
9 int rem = (int)(prefix[n] % p);
10 if (rem == 0) return 0;
11 int minLen = n;
12 for (int j = 1; j <= n; j++) {
13 for (int i = 0; i < j; i++) {
14 if ((prefix[j] - prefix[i]) % p == rem && (j - i) < n) {
15 minLen = Math.min(minLen, j - i);
16 }
17 }
18 }
19 return minLen == n ? -1 : minLen;
20 }
21 }
22
23 public static void main(String[] args) {
24 Solution sol = new Solution();
25 int[] nums = {3, 1, 4, 2};
26 int p = 6;
27 System.out.println("Min Subarray Length: " + sol.minSubarray(nums, p));
28 }
29}

Time & Space Complexity

  • Time complexity: O(n^2) — Precomputing prefix mods is O(n), and the nested index loop takes O(n2) comparisons.
  • Space complexity: O(n) — O(n) memory to store the prefix modulo array.

3. Prefix Modulo + Hash Map (Optimal)

Intuition

Let rem = sum(nums) % p. If rem == 0, return 0. We need to find the shortest subarray (i, j] where (prefix[j] - prefix[i]) % p == rem. Rearranging gives: prefix[i] % p = (prefix[j] % p - rem + p) % p. By storing the most recent index of each prefix modulo in a hash map (initialized with {0: -1}), we can look up the needed prefix[i] % p in O(1) time. Updating the map with index j ensures we always find the shortest subarray.

When to apply: Use as the optimal O(n) time solution for finding the shortest subarray with modular remainder constraints.

Prefix Remainder Hash Map (O(N) Time, O(N) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
To minimize length, we want the most recent (latest) index of the matching remainder
Visual state
Values and pointers at this exact step
pointers
S
3
1
4
2
0
↑ init
1
2
3
Variables at this step
targetRem
4
minLen
4
latestMap
{"0":-1}
Check / comparison
Total sum = 10 % 6 = 4 (targetRem = 4). Seed latestMap = { 0: -1 }
Decision / next transition
We need a prior remainder = (currRem - targetRem + p) % p.
Why this step matters

To minimize length, we want the most recent (latest) index of the matching remainder.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.HashMap;
2import java.util.Map;
3
4public class Main {
5 public static class Solution {
6 public int minSubarray(int[] nums, int p) {
7 long total = 0;
8 for (int x : nums) total += x;
9 int rem = (int)(total % p);
10 if (rem == 0) return 0;
11
12 Map<Integer, Integer> map = new HashMap<>();
13 map.put(0, -1);
14 int n = nums.length;
15 int minLen = n;
16 long cur = 0;
17
18 for (int i = 0; i < n; i++) {
19 cur = (cur + nums[i]) % p;
20 int target = (int)((cur - rem + p) % p);
21 if (map.containsKey(target)) {
22 minLen = Math.min(minLen, i - map.get(target));
23 }
24 map.put((int)cur, i);
25 }
26 return minLen == n ? -1 : minLen;
27 }
28 }
29
30 public static void main(String[] args) {
31 Solution sol = new Solution();
32 int[] nums = {3, 1, 4, 2};
33 int p = 6;
34 System.out.println("Min Subarray Length: " + sol.minSubarray(nums, p));
35 }
36}

Time & Space Complexity

  • Time complexity: O(n) — A single pass over nums doing O(1) average hash map lookups takes O(n) total time.
  • Space complexity: O(min(n, p)) — The hash map stores at most min(n, p) distinct remainder entries.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute ForceO(N^2)O(1)Check every subarray (i, j), compute (totalSum - subarraySum) % p == 0, find minimum length.Testing all N2 pairs.
2.Better — Prefix Table SearchO(N^2)O(N)Precompute prefix sum table and test all (i, j) range remainders in O(1).Pairwise enumeration.
3.Optimal — Prefix Remainder Hash MapOptimalO(N)O(min(N, P))Store latest index of each remainder in hash map. Single pass O(N) lookup.None; industry-standard optimal solution.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • totalSum % p == 0: Already divisible, return 0 immediately.
  • minLen == N: Whole array would need to be removed (e.g. nums=[1, 2, 3], p=7) -> forbidden, return -1.
  • Negative modulo values in C++/Java: adding + p before modulo (curMod - targetRem + p) % p prevents negative index lookups.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Make Sum Divisible by P?

2.Why is the brute force approach suboptimal for large inputs in Make Sum Divisible by P?

3.Which data structure or technique enables the optimal solution for Make Sum Divisible by P?

Back to DSA Sheet