LeetCode 1590: Make Sum Divisible by P

Explanation:

To solve this problem, we can use the concept of prefix sums and modulo arithmetic. First, we calculate the total sum of the elements in the given array. Then, we find the target sum that we need to reach to make the remaining elements divisible by p.

Next, we iterate through the array and calculate the prefix sum modulo p at each index. We store these remainders in a HashMap along with their corresponding indices. If the current prefix sum modulo p is x and we need to reach the target remainder y, we can remove the subarray between the current index and the index stored in the HashMap where the remainder was ((x - y) % p + p) % p.

If at any point the prefix sum modulo p is equal to the target remainder y, we can consider the subarray from the beginning up to the current index as the subarray to be removed.

Finally, we return the length of the smallest subarray that needs to be removed or -1 if it's impossible.

• Time complexity: O(n)
• Space complexity: O(n)

:

class Solution {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        int target = 0;
        for (int num : nums) {
            target = (target + num) % p;
        }
        if (target == 0) {
            return 0;
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int prefixSum = 0;
        int minLen = n;
        int currMod = 0;
        for (int i = 0; i < n; i++) {
            prefixSum = (prefixSum + nums[i]) % p;
            int targetMod = (prefixSum - target + p) % p;
            if (map.containsKey(targetMod)) {
                minLen = Math.min(minLen, i - map.get(targetMod));
            }
            map.put(currMod, i);
            currMod = prefixSum;
        }
        
        return minLen == n ? -1 : minLen;
    }
}