(sum % p) 1590. Make Sum Divisible by P

T: O(n)
S: O(n)

class Solution {
    public int minSubarray(int[] nums, int p) {
        int sum = 0;
        for (int num : nums) {
            sum = ((sum + num) %p); // so %p every time , it's the same remainder!
        }
        int target = sum % p;
        if (target == 0) {
            return 0;
        }

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int curSum = 0;
        int result = nums.length;
        for (int i = 0; i < nums.length; i++) {
            curSum += nums[i];
            curSum %= p;
            if (map.containsKey((curSum - target + p)%p)) {
                result = Math.min(result, i - map.get((curSum - target + p)%p));
            }
            map.put(curSum, i);
        }
        return result == nums.length ? -1 : result;
    }
}

/**
T: O(n)
S: O(n)


sum the array
% by p
find the remainder(this is what we want to remove, so now problem become find a subarray sum == remainder)
-> (like  subarray sum equals k problem)


find any subarray can be the remainder -> so question become subarray equals remainder (like  subarray sum equals k problem)

but for not overflow, curSum and map key, all %p

because anyway, this remainder can't be mod by %p, and we want to find a "prefix_sum - target is % by p exists in map""


find a subarray sum = k



                    k
|--------------|--------|
 prefix_sum - k           prefix_sum
 */