medium Make Sum Divisible by P

Problem Statement

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

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

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

Examples

Example 1:

• Input: nums = [5, 9, 7, 8], P = 5
• Expected Output: 1
• Justification: Removing the subarray [9] results in a new array [5, 7, 8] whose sum is 20, which is divisible by 5.

Example 2:

• Input: nums = [6, 4, 3, 2, 7, 6, 2], P = 10
• Expected Output: 0
• Justification: We don't need to remove any element from the array, as the sum of all array elements is divisible by 10.

Example 3:

• Input: nums = [8, 19, 4, 3], P = 10
• Expected Output: 1
• Justification: By removing the subarray [4], we get a new array [8, 19, 3] with a sum of 30, Which is divisible by 10.

Solution

To solve this problem, we adopt a two-pronged strategy focusing on prefix sums and hash mapping. Initially, we calculate the total sum of the array and determine the excess or deficit with respect to P required to make the sum divisible by P. Recognizing that removing a subarray to adjust the total sum to a multiple of P mirrors finding a segment whose sum equals this excess or deficit, we proceed to track prefix sums and their indices.

This approach is underpinned by the insight that if two prefix sums have the same remainder when divided by P, the segment between them contributes a sum that is a multiple of P. Consequently, by maintaining a hash map of the earliest occurrence of each remainder, we can efficiently identify the minimum length of a subarray that, when removed, leaves the array's sum divisible by P. This method is not only intuitive but also leverages the efficiency of hash maps for quick lookups, rendering it a potent solution for the problem at hand.

Step-by-Step Algorithm

1. Initialize Variables:

   • Calculate the total sum of the array elements and find its remainder when divided by P (totalSum % P). This will help in identifying the excess amount that needs to be addressed by removing a subarray.
   • Initialize an empty hash map (remainderMap) to store the prefix sum remainders as keys and their corresponding indices as values. Insert a base case into the hash map with 0 as the key and -1 as the value. This represents the prefix sum before the array starts, facilitating scenarios where the required subarray starts from index 0.
   • Define variables for the current sum (currSum), set initially to 0, and the minimum length of the subarray to be removed (minLen), set initially to an arbitrarily large value (like Integer.MAX_VALUE in Java or float('inf') in Python).

2. Iterate Through the Array:

   • For each element in the array, add it to currSum and calculate the remainder of currSum when divided by P.
   • Calculate the complement of the current remainder with respect to the total excess ((currSum - totalSum + P) % P). This step identifies what remainder we need to find in the hash map to form a continuous subarray whose removal could potentially make the total sum divisible by P.

3. Update HashMap and Minimum Length:

   • If the complement calculated in the previous step exists in remainderMap, it means there exists a previous prefix sum that, when subtracted from the current prefix sum, results in a sum that is a multiple of P. Calculate the length of this subarray and update minLen if this length is smaller than the current minLen.
   • Update remainderMap with the current prefix sum remainder as the key and the current index as the value. This step is crucial for keeping track of the earliest occurrence of each remainder.

4. Finalize Result:

   • After iterating through the entire array, check if minLen is still set to its initial large value or equals the length of the array. If so, return -1, indicating that it's not possible to remove any subarray to make the sum divisible by P.
   • Otherwise, return minLen as the minimum length of the subarray that needs to be removed.

Algorithm Walkthrough

Let's consider the input: nums = [5, 9, 7, 8], P = 5

• Total Sum Calculation:

  • Total sum of [5, 9, 7, 8] is 29. 29 % 5 = 4. So, we need to adjust the total sum to be divisible by 5 by addressing this excess of 4.

• Initialization:

  • remainderMap = {0: -1}
  • totalSum % P = 4, currSum = 0, minLen = inf

• Iteration 1:

  • currSum with first element 5: currSum = (0 + 5) % 5 = 0
  • Complement to find: (0 - 4 + 5) % 5 = 1. Complement 1 doesn't exist in remainderMap.
  • remainderMap updated to {0: 0}

• Iteration 2:

  • currSum with second element 9: currSum = (0 + 9) % 5 = 4
  • Complement to find: (4 - 4 + 5) % 5 = 0. Complement 0 exists in remainderMap.
  • Update minLen to 1 - 0 = 1.
  • remainderMap updated to {0: 0, 4: 1}

• Iteration 3:

  • currSum with third element 7: currSum = (4 + 7) % 5 = 1
  • Complement to find: (1 - 4 + 5) % 5 = 2. Complement 2 does not exist in remainderMap.
  • remainderMap updated to {0: 0, 4: 1, 1: 2}

• Iteration 4:

  • currSum with fourth element 8: currSum = (1 + 8) % 5 = 4
  • Complement to find: (4 - 4 + 5) % 5 = 0. Complement 0 exists in remainderMap.
  • minLen could be updated to 3 - 0 = 3, but since 1 < 3, minLen remains 1.
  • remainderMap final {0: 0, 4: 1, 1: 2}

• Final Result:

  • The minimum length of the subarray that needs to be removed to make the sum divisible by P is 1. This corresponds to the removal of [9] to adjust the sum.

Code

import java.util.HashMap; // Import statement for HashMap

public class Solution {

  // Method to find the minimum subarray length to remove for making the sum divisible by P
  public int minSubarray(int[] nums, int P) {
    int totalSum = 0;
    // Calculate the total sum of the array elements
    for (int num : nums) {
      totalSum = (totalSum + num) % P;
    }
    // If totalSum is already divisible by P, no need to remove any subarray
    if (totalSum == 0) return 0;
    // HashMap to store the earliest index where each remainder is found
    HashMap<Integer, Integer> remainderMap = new HashMap<>();
    remainderMap.put(0, -1); // Base case: to handle the case when subarray starts from index 0
    int minLen = Integer.MAX_VALUE, currSum = 0;
    // Iterate through the array to find the minimum length subarray to remove
    for (int i = 0; i < nums.length; i++) {
      currSum = (currSum + nums[i]) % P;
      int complement = (currSum - totalSum + P) % P;
      // If complement exists in remainderMap, calculate the possible minimum length
      if (remainderMap.containsKey(complement)) {
        minLen = Math.min(minLen, i - remainderMap.get(complement));
      }
      // Update the remainderMap with the current remainder and its index
      remainderMap.put(currSum, i);
    }
    // Return the minimum length found, ensuring it's not the entire array length
    return minLen == Integer.MAX_VALUE || minLen == nums.length ? -1 : minLen;
  }

  // Main method to test the solution with example inputs
  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(solution.minSubarray(new int[] { 5, 9, 7, 8 }, 5));
    System.out.println(
      solution.minSubarray(new int[] { 6, 4, 3, 2, 7, 6, 2 }, 10)
    );
    System.out.println(solution.minSubarray(new int[] { 8, 19, 4, 3 }, 10));
  }
}

Complexity Analysis

• Time Complexity: The algorithm iterates through the array once, making the time complexity , where N is the length of the array. The operations within each iteration (e.g., updating the hash map, calculating remainders) are constant time.
• Space Complexity: The space complexity is also due to the hash map that stores up to N different remainders and their indices.