Logic Explanation
1 Find remainder: Calculate the total sum of the array and its remainder when divided by p. This remainder is what we need to "cancel out" by removing a subarray.
2 Prefix sums: As we go through the array, we calculate the running sum (prefix sum) and store its remainder modulo p in a hash map.
3 Find subarray to remove: For each prefix, check if removing a previous subarray would result in the remaining sum being divisible by p. This is done by checking the hash map for the right remainder.
4 Track smallest subarray: Keep track of the smallest such subarray and return its length, or return -1 if no valid subarray exists.
Added solution for day 3
Logic Explanation 1 Find remainder: Calculate the total sum of the array and its remainder when divided by p. This remainder is what we need to "cancel out" by removing a subarray.
2 Prefix sums: As we go through the array, we calculate the running sum (prefix sum) and store its remainder modulo p in a hash map.
3 Find subarray to remove: For each prefix, check if removing a previous subarray would result in the remaining sum being divisible by p. This is done by checking the hash map for the right remainder.
4 Track smallest subarray: Keep track of the smallest such subarray and return its length, or return -1 if no valid subarray exists.