1590. Make Sum Divisible by P LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1590. Make Sum Divisible by P LeetCode Solution with the best time and space complexity. The solution to Make Sum Divisible by P problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Make Sum Divisible by P solution in C++
Make Sum Divisible by P solution in Java
Make Sum Divisible by P solution in Python
Additional Resources

1590. Make Sum Divisible by P LeetCode Solution image

Problem Statement of Make Sum Divisible by P

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1590. Make Sum Divisible by P LeetCode Solution in C++

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

    unordered_map<int, int> prefixToIndex{{0, -1}};
    int ans = nums.size();
    int prefix = 0;

    for (int i = 0; i < nums.size(); ++i) {
      prefix += nums[i];
      prefix %= p;
      const int target = (prefix - remainder + p) % p;
      if (const auto it = prefixToIndex.find(target);
          it != prefixToIndex.cend())
        ans = min(ans, i - it->second);
      prefixToIndex[prefix] = i;
    }

    return ans == nums.size() ? -1 : ans;
  }
};
/* code provided by PROGIEZ */

1590. Make Sum Divisible by P LeetCode Solution in Java

class Solution {
  public int minSubarray(int[] nums, int p) {
    final long sum = Arrays.stream(nums).asLongStream().sum();
    final int remainder = (int) (sum % p);
    if (remainder == 0)
      return 0;

    int ans = nums.length;
    int prefix = 0;
    Map<Integer, Integer> prefixToIndex = new HashMap<>();
    prefixToIndex.put(0, -1);

    for (int i = 0; i < nums.length; ++i) {
      prefix += nums[i];
      prefix %= p;
      final int target = (prefix - remainder + p) % p;
      if (prefixToIndex.containsKey(target))
        ans = Math.min(ans, i - prefixToIndex.get(target));
      prefixToIndex.put(prefix, i);
    }

    return ans == nums.length ? -1 : ans;
  }
}
// code provided by PROGIEZ

1590. Make Sum Divisible by P LeetCode Solution in Python

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

    ans = len(nums)
    prefix = 0
    prefixToIndex = {0: -1}

    for i, num in enumerate(nums):
      prefix += num
      prefix %= p
      target = (prefix - remainder + p) % p
      if target in prefixToIndex:
        ans = min(ans, i - prefixToIndex[target])
      prefixToIndex[prefix] = i

    return -1 if ans == len(nums) else ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents