Make Sum Divisible by P

In this page, we will solve the Make Sum Divisible by P problem using different approaches. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

Problem Description

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 guaranteed that there is an answer. If this is not possible, return -1.

Examples

Example 1:

Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: The sum of the array is 10, and the sum modulo 6 is 4. 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: The sum of the array is 16, and the sum modulo 9 is 7. We can remove the subarray [5,2], and the sum of the remaining elements is 9, which is divisible by 9.

Constraints

• $1 \leq nums.length \leq 10^5$
• $1 \leq nums[i] \leq 10^9$
• $1 \leq p \leq 10^9$

---

Solution for Make Sum Divisible by P

Intuition and Approach

To solve the problem, we need to remove the smallest subarray such that the sum of the remaining elements is divisible by p. One efficient way to approach this is by using the prefix sum and a hash map.

• Prefix Sum and HashMap
• Brute Force

Approach 1: Prefix Sum and HashMap

We calculate the prefix sum and use a hash map to store the remainder when each prefix sum is divided by p. This allows us to quickly find the smallest subarray whose removal makes the remaining sum divisible by p.

Implementation

Live Editor

function makeSumDivisibleByP() {
  const nums = [3, 1, 4, 2];
  const p = 6;

  const minSubarray = function(nums, p) {
    const totalSum = nums.reduce((acc, num) => acc + num, 0);
    const remainder = totalSum % p;
    if (remainder === 0) return 0;

    const prefixSum = new Map();
    prefixSum.set(0, -1);

    let currentSum = 0;
    let minLength = Infinity;

    for (let i = 0; i < nums.length; i++) {
      currentSum += nums[i];
      const currentRemainder = currentSum % p;

      const targetRemainder = (currentRemainder - remainder + p) % p;
      if (prefixSum.has(targetRemainder)) {
        minLength = Math.min(minLength, i - prefixSum.get(targetRemainder));
      }

      prefixSum.set(currentRemainder, i);
    }

    return minLength === Infinity ? -1 : minLength;
  };

  const result = minSubarray(nums, p);
  return (
    <div>
      <p>
        <b>Input:</b> nums = {JSON.stringify(nums)}, p = {p}
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}

Result

Loading...

Code in Different Languages

JavaScript

Written by @manishh12

 function minSubarray(nums, p) {
   const totalSum = nums.reduce((acc, num) => acc + num, 0);
   const remainder = totalSum % p;
   if (remainder === 0) return 0;

   const prefixSum = new Map();
   prefixSum.set(0, -1);

   let currentSum = 0;
   let minLength = Infinity;

   for (let i = 0; i < nums.length; i++) {
     currentSum += nums[i];
     const currentRemainder = currentSum % p;

     const targetRemainder = (currentRemainder - remainder + p) % p;
     if (prefixSum.has(targetRemainder)) {
       minLength = Math.min(minLength, i - prefixSum.get(targetRemainder));
     }

     prefixSum.set(currentRemainder, i);
   }

   return minLength === Infinity ? -1 : minLength;
 }

TypeScript

Written by @manishh12

 function minSubarray(nums: number[], p: number): number {
   const totalSum = nums.reduce((acc, num) => acc + num, 0);
   const remainder = totalSum % p;
   if (remainder === 0) return 0;

   const prefixSum = new Map<number, number>();
   prefixSum.set(0, -1);

   let currentSum = 0;
   let minLength = Infinity;

   for (let i = 0; i < nums.length; i++) {
     currentSum += nums[i];
     const currentRemainder = currentSum % p;

     const targetRemainder = (currentRemainder - remainder + p) % p;
     if (prefixSum.has(targetRemainder)) {
       minLength = Math.min(minLength, i - prefixSum.get(targetRemainder)!);
     }

     prefixSum.set(currentRemainder, i);
   }

   return minLength === Infinity ? -1 : minLength;
 }

Python

Written by @manishh12

 class Solution:
     def minSubarray(self, nums: List[int], p: int) -> int:
         total_sum = sum(nums)
         remainder = total_sum % p
         if remainder == 0:
             return 0

         prefix_sum = {0: -1}
         current_sum = 0
         min_length = float('inf')

         for i, num in enumerate(nums):
             current_sum += num
             current_remainder = current_sum % p

             target_remainder = (current_remainder - remainder + p) % p
             if target_remainder in prefix_sum:
                 min_length = min(min_length, i - prefix_sum[target_remainder])

             prefix_sum[current_remainder] = i

         return min_length if min_length != float('inf') else -1

Java

Written by @manishh12

 import java.util.HashMap;
 import java.util.Map;

 class Solution {
     public int minSubarray(int[] nums, int p) {
         int totalSum = 0;
         for (int num : nums) {
             totalSum += num;
         }
         int remainder = totalSum % p;
         if (remainder == 0) {
             return 0;
         }

         Map<Integer, Integer> prefixSum = new HashMap<>();
         prefixSum.put(0, -1);

         int currentSum = 0;
         int minLength = Integer.MAX_VALUE;

         for (int i = 0; i < nums.length; i++) {
             currentSum += nums[i];
             int currentRemainder = currentSum % p;

             int targetRemainder = (currentRemainder - remainder + p) % p;
             if (prefixSum.containsKey(targetRemainder)) {
                 minLength = Math.min(minLength, i - prefixSum.get(targetRemainder));
             }

             prefixSum.put(currentRemainder, i);
         }

         return minLength == Integer.MAX_VALUE ? -1 : minLength;
     }
 }

C++

Written by @manishh12

 #include <vector>
 #include <unordered_map>
 #include <algorithm>
 #include <numeric>

 class Solution {
 public:
     int minSubarray(std::vector<int>& nums, int p) {
         int totalSum = std::accumulate(nums.begin(), nums.end(), 0);
         int remainder = totalSum % p;
         if (remainder == 0) return 0;

         std::unordered_map<int, int> prefixSum;
         prefixSum[0] = -1;

         int currentSum = 0;
         int minLength = INT_MAX;

         for (int i = 0; i < nums.size(); ++i) {
             currentSum += nums[i];
             int currentRemainder = currentSum %```
p;

             int targetRemainder = (currentRemainder - remainder + p) % p;
             if (prefixSum.count(targetRemainder)) {
                 minLength = std::min(minLength, i - prefixSum[targetRemainder]);
             }

             prefixSum[currentRemainder] = i;
         }

         return minLength == INT_MAX ? -1 : minLength;
     }
 };

Complexity Analysis

• Time Complexity: $O(n)$, where $n$ is the length of the nums array.
• Space Complexity: $O(n)$, for storing the prefix sum and remainder in the hash map.

tip

By using either the prefix sum and hash map approach or the brute force approach, we can efficiently solve the Make Sum Divisible by P problem. The choice of implementation language depends on the specific requirements and constraints of the problem.

References

• LeetCode Problem: Make Sum Divisible by P

• Solution Link: Make Sum Divisible by P Solution on LeetCode

• Authors LeetCode Profile: Manish Kumar Gupta