Skip to main content

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≤nums.length≤1051 \leq nums.length \leq 10^5
  • 1≤nums[i]≤1091 \leq nums[i] \leq 10^9
  • 1≤p≤1091 \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.

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​

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;
}

Complexity Analysis​

  • Time Complexity: O(n)O(n), where nn is the length of the nums array.
  • Space Complexity: O(n)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​