Min Subarray Divisible By P

XXX. Min Subarray Divisible by p

Prefix Sum

Hash Table

Greedy

Problem Statement:

You are given an array nums and a positive integer p. Remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.

Approach:

1. Calculate the total sum of the array modulo p to find the target remainder.
2. Use a hash map to track prefix sum remainders and their indices.
3. As you iterate through the array, calculate the current prefix sum modulo p.
   • If you find a previously seen remainder that allows removing a subarray to meet the target, calculate the subarray length and update the minimum length.
4. Return the minimum length if valid; otherwise, return -1.

Complexity:

Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the hash map storing prefix sums.

Java Implementation:

// Basically becomes minsubarray problem
// Find smallest subarray that equals the remainder 
// Don't be scared of the (int needed = (currentSum - target + p) % p) 
// Just pretened the "p" don't exist, it's a way to avoid negatives 
public int minSubarray(int[] nums, int p) {
    int n = nums.length;
    int totalSum = 0;

    // Step 1: Calculate total sum and target remainder
    for (int num : nums) {
        totalSum = (totalSum + num) % p;
    }

    int target = totalSum % p;
    if (target == 0) return 0; // The array is already divisible by p
    
    // Step 2: Use a hash map to track prefix sum mod p
    HashMap modMap = new HashMap<>();
    modMap.put(0, -1); // To handle the case where the whole prefix is the answer
    int currentSum = 0;
    int minLen = n;

    // Step 3: Iterate over the array
    for (int i = 0; i < n; ++i) {
        currentSum = (currentSum + nums[i]) % p;

        // Calculate what we need to remove
        int needed = (currentSum - target + p) % p;

        // If we have seen the needed remainder, we can consider this subarray
        if (modMap.containsKey(needed)) 
            minLen = Math.min(minLen, i - modMap.get(needed));
        

        // Store the current remainder and index
        modMap.put(currentSum, i);
    }

    // Step 4: Return result
    return minLen == n ? -1 : minLen;
}