Skip to main content
Talentd

Make Sum Divisible by P - Solution & Explanation

MediumArrayHash TablePrefix Sum19 min readAsked at: Amazon, Microsoft, Samsung +4
Practice this problem

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 block of elements in the array.

 

Example 1:

Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.

Example 2:

Input: nums = [6,3,5,2], p = 9
Output: 2
Explanation: We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.

Example 3:

Input: nums = [1,2,3], p = 3
Output: 0
Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

 

Constraints:

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

Approach Overview

Problem Overview: You are given an integer array nums and an integer p. Remove the smallest contiguous subarray so that the sum of the remaining elements becomes divisible by p. The removed subarray cannot be the entire array.

The key observation: if the total array sum has remainder r = total % p, you must remove a subarray whose sum also has remainder r. The task becomes finding the shortest subarray with that remainder.

Approach 1: Brute Force Subarray Search (O(nĀ²) time, O(1) space)

Check every possible subarray and compute its sum. For each candidate, subtract its sum from the total and verify whether the remaining sum becomes divisible by p. This requires nested loops over the array and repeated modulo checks. While simple to implement, it performs poorly for large inputs because there are O(nĀ²) possible subarrays. Useful only for understanding the problem or verifying small cases.

Approach 2: Prefix Sum and Remainder with HashMap (O(n) time, O(n) space)

Compute prefix sums while tracking each prefix remainder modulo p. Let target = total_sum % p. While iterating, maintain prefix % p and look for a previous prefix remainder that satisfies (current - target) % p. A hash table maps each remainder to its most recent index, allowing constant-time lookup. This transforms the search for a valid removable subarray into a prefix remainder matching problem using prefix sums. The result is the minimum length between matching indices.

The insight: if two prefix sums differ by remainder target modulo p, the subarray between them has exactly the remainder needed to remove.

Approach 3: Sliding Window with Two Pointers (O(n) time, O(1) space)

A two-pointer technique can be applied when reasoning about subarray sums incrementally. Expand the right pointer to accumulate a running sum and shrink from the left when conditions exceed the required remainder window. This approach tries to maintain a candidate window whose sum modulo p matches the required remainder. It avoids extra memory and relies on pointer movement over the array. While less common than the prefix-hash solution, it works when the window behavior can be controlled with modular checks.

Recommended for interviews: The Prefix Sum + HashMap approach is what interviewers expect. It reduces a seemingly complex removal problem into a modular prefix lookup and runs in linear time. Brute force shows you understand the condition, but the prefix remainder trick demonstrates algorithmic maturity.

Approach 1: Prefix Sum and Remainder with HashMap

This approach involves first calculating the remainder of the sum of the given array with respect to p. By maintaining a prefix sum and using the properties of modular arithmetic, we can determine the shortest subarray whose removal results in a remainder of zero.

This implementation calculates the prefix sum and stores remainders in a hashmap. By checking if the target remainder exists in the hashmap, we find the minimal subarray that aligns with our requirement. We update the hashmap with current prefix sums iteratively.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for storing prefix sums in the hashmap.

Try this approach in the editor ā†’

Approach 2: Sliding Window with Two Pointers

This approach makes use of a sliding window or two-pointer technique to identify the minimal subarray which upon removal makes the sum of the remaining elements divisible by p.

The Java solution uses a HashMap to keep track of prefix sums as keys, linked to their indexes. The final loop computes prefix sums iteratively and checks for the desired remainder, computing the minimal subarray, if applicable.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for maintaining the hashmap.

Try this approach in the editor ā†’

Approach 3: Prefix Sum + Hash Table

First, we calculate the sum of all elements in the array nums modulo p, denoted as k. If k is 0, it means the sum of all elements in the array nums is a multiple of p, so we directly return 0.

If k is not 0, we need to find the shortest subarray such that removing this subarray makes the sum of the remaining elements modulo p equal to 0.

We can traverse the array nums, maintaining the current prefix sum modulo p, denoted as cur. We use a hash table last to record the last occurrence of each prefix sum modulo p.

If there exists a subarray ending at nums[i] such that removing this subarray makes the sum of the remaining elements modulo p equal to 0, we need to find a previous prefix sum modulo p equal to target at position j such that (target + k - cur) bmod p = 0. If found, we can remove the subarray nums[j+1,..i] to make the sum of the remaining elements modulo p equal to 0.

Therefore, if there exists a target = (cur - k + p) bmod p, we can update the answer to min(ans, i - j). Then, we update last[cur] to i. We continue traversing the array nums until the end to get the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Prefix Sum and Remainder with HashMap

Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for storing prefix sums in the hashmap.

Sliding Window with Two Pointers

Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(n), for maintaining the hashmap.

Prefix Sum + Hash Tableā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray CheckO(n^2)O(1)Small arrays or when explaining the basic idea before optimization
Prefix Sum + HashMapO(n)O(n)General case and interview-preferred optimal solution
Sliding Window Two PointersO(n)O(1)When minimizing extra memory and reasoning with window-based sums

Video Solution

Make Sum Divisible by P | Simplest Explanation | Full Dry Run | Leetcode 1590 | codestorywithMIK ā€¢ codestorywithMIK ā€¢ 25,361 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Make Sum Divisible by P easy or hard?
Make Sum Divisible by P is rated Medium difficulty on LeetCode with an acceptance rate around 40%. The challenge comes from recognizing the modular prefix sum pattern rather than brute-force checking all subarrays.
Make Sum Divisible by P Python/Java solution
Most implementations use the prefix sum + hash map technique. Python solutions typically use a dictionary for remainder lookup, while Java uses a HashMap. Both versions iterate once through the array and maintain prefix modulo values to compute the minimum subarray length.
How to solve Make Sum Divisible by P in O(n)?
First compute total_sum % p. If the remainder is r, you need to remove a subarray whose sum % p equals r. While scanning the array, maintain prefix_sum % p and store previous remainders in a hash map. For each index, check if (current_remainder - r + p) % p exists in the map to get the shortest valid subarray.
What is the best approach for Make Sum Divisible by P?
The best approach uses prefix sums with a hash map to track remainders modulo p. Compute the total remainder and search for the shortest subarray whose remainder matches it. This method runs in O(n) time with O(n) extra space and efficiently finds the minimum removable subarray.
Is Make Sum Divisible by P asked at Google/Amazon/Meta?
Variants of prefix sum with modular arithmetic frequently appear in interviews at companies like Google, Amazon, and Meta. Problems involving subarray sums, modulo operations, and hash maps are common because they test algorithmic pattern recognition and hash-based optimization.
What data structure is used in Make Sum Divisible by P?
The core data structure is a hash map that stores prefix remainder values and their indices. Combined with prefix sums, this structure allows constant-time lookup to determine whether a previous prefix can form the required removable subarray.
What is the time complexity of Make Sum Divisible by P?
The optimal solution runs in O(n) time because the array is processed once while maintaining prefix remainders in a hash map. Each step performs constant-time lookups and updates. Space complexity is O(n) due to storing remainders.

Ready to solve this problem?

Practice Make Sum Divisible by P with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Divisibility Array of a String

Next

Subarray Sums Divisible by K