Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.
Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.
A subarray is defined as a contiguous block of elements in the array.
 
Example 1:
Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.

Example 2:
Input: nums = [6,3,5,2], p = 9
Output: 2
Explanation: We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.

Example 3:
Input: nums = [1,2,3], p = 3
Output: 0
Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

Example 4:
Input: nums = [1,2,3], p = 7
Output: -1
Explanation: There is no way to remove a subarray in order to get a sum divisible by 7.

Example 5:
Input: nums = [1000000000,1000000000,1000000000], p = 3
Output: 0

 
Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= p <= 109

Difficulty: interview

Starter code:

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        

Solutions:
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        need = sum(nums) % p
        if need == 0:
            return 0
        pos = {0: -1}
        total = 0
        ans = float('inf')
        for i, num in enumerate(nums):
            total = (total + num) % p
            target = (total - need) % p
            if target in pos:
                ans = min(ans, i - pos[target])
            pos[total] = i
        return ans if ans < len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        curr_acc_sum = sum(nums)
        rem = curr_acc_sum % p
        if rem == 0:
            return 0
        h_rem, min_len = {0: -1}, len(nums)
        cur_rem = 0
        for i in range(len(nums)):
            cur_rem = (cur_rem + nums[i]) % p
            h_rem[cur_rem] = i
            # print([rem, cur_rem, (cur_rem - rem) % p])
            if (cur_rem - rem) % p in h_rem:
                # print([min_len, i - h_rem[(cur_rem - rem) % p]])
                min_len = min(min_len, i - h_rem[(cur_rem - rem) % p])
        if min_len == len(nums):
            return -1
        return min_len
            
                
            


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        remain = sum(nums) % p
        if remain == 0:
            return 0
        dic = {0:-1}
        presum, res = 0, float('inf')
        for i, num in enumerate(nums):
            presum += num
            cur_remain = presum % p
            dic[cur_remain] = i
            target = (cur_remain - remain) % p
            if target in dic:
                res = min(res, i - dic[target])
        return res if res < len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        cum_sum = [0]
        for number in nums:
            cum_sum.append((cum_sum[-1] + number) % p)
        overall_sum = cum_sum[-1]
        if overall_sum % p == 0: return 0
        self.memory = {}
        longest_dist = len(nums) + 5
        for j, cur_sum in enumerate(cum_sum[:-1]):
            if cur_sum % p == 0:
                longest_dist = min(longest_dist, len(cum_sum) - j - 1)
            if (overall_sum - cur_sum) % p in self.memory:
                i = self.memory[(overall_sum - cur_sum) % p]
                longest_dist = min(longest_dist, j - i)
            self.memory[(- cur_sum) % p] = j
            
        if longest_dist >= len(nums):
            return -1
        return longest_dist


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        s = 0
        ss = sum(nums) % p
        if ss == 0: return 0
        h = {}
        h[0] = -1
        import sys
        ans = sys.maxsize
        for i, e in enumerate(nums):
            s += e
            # s-x-ss
            c = (p - (ss - s) % p) % p
            # if ss == e % p: ans = 1
            if c in h:
                ans = min(ans, i - h[c])
            h[s % p] = i
        if ans == len(nums): ans = -1
        return ans        

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        # remove smallest thing from centert
        tot=sum(nums)
        need=sum(nums)%p
        if need==0:
            return 0
        seen={0:-1}
        curr=0
        ret=len(nums)
        for i,num in enumerate(nums):
            curr=(curr+num)%p
            other=(curr-need)%p
            if other in seen:
                my_best=i-seen[other]
                if my_best<ret:
                    ret=my_best
            seen[curr]=i
        return ret if ret!=len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        prefix = [0 for _ in range(n+1)]
        for i in range(n):
            prefix[i+1] = prefix[i] + nums[i]
            
        res = prefix[n] % p
        if res == 0:
            return 0
        
        loc = {}
        ans = float('inf')
        for i, pre in enumerate(prefix):
            d = (pre - res) % p
            if d in loc:
                ans = min(ans, i - loc[d])
            loc[pre % p] = i
            
        return -1 if ans == float('inf') or ans == n else ans

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total = sum(nums)
        
        m = total % p
        if m == 0:
            return 0
        
        current_sum = 0
        IMPOSSIBLE = len(nums)
        ans = IMPOSSIBLE
        mod_last_positions = {0:-1}
        
        for idx, num in enumerate(nums):
            current_sum += num
            if (current_sum - m) % p in mod_last_positions:
                ans = min(ans, idx - mod_last_positions[(current_sum-m)%p])
            mod_last_positions[current_sum % p] = idx
            #print(mod_last_positions)
            #print(ans, current_sum)
            
        return ans if ans != IMPOSSIBLE else -1
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total_remainder = sum(nums) % p
        prev = {}
        res = len(nums)
        current_sum = 0
        prev[current_sum] = 0
        for i in range(len(nums)):
            current_sum = (current_sum + nums[i]) % p
            prev[current_sum] = i + 1
            other = (current_sum - total_remainder) % p
            if other in prev:
                res = min(res, i + 1 - prev[other])
        return res if res < len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n=len(nums)
        s=sum(nums)
        k=s%p
        if not k:
            return 0
        d={0:-1}
        
        sumJ=0
        res=float('inf')
        for i,num in enumerate(nums):
            sumJ+=num
            '''
            (sumJ-sumI)%p=k
            sumJ-sumI=n*p+k
            sumI=sumJ-np-k
            sumI%p=(sumJ-np-k)%p=(sumJ%p-np%p-k%p)%p=(sumJ%p-k%p)%p
            '''
            
            sumI_mod_p=(sumJ%p-k%p)%p
            if sumI_mod_p in d:
                res=min(res,i-d[sumI_mod_p])
            d[sumJ%p]=i
        return res if res<n else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        tar = sum(nums) % p
        if tar == 0:
            return 0
        rec = {0: -1}
        cur = 0
        res = len(nums)
        for i, v in enumerate(nums):
            cur = (cur + v) % p
            t = (cur - tar + p) % p
            if t in rec:
                res = min(res, i - rec[t])
            rec[cur] = i
        return -1 if res == len(nums) else res


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total = sum(nums) 
        remainder = total % p
        if not remainder:
            return 0
        ans = float('inf') 
        presum = [0]
        remainders = {0: -1}
        for i, n in enumerate(nums):
            presum.append(presum[-1] + n)
            r = ((cr := presum[-1] % p) - remainder) % p
            if r in remainders:
                ans = min(ans, i - remainders[r])
            remainders[cr] = i
        return ans if ans < len(nums) else -1

class Solution:
    def minSubarray(self, A, p):
        need = sum(A) % p
        dp = {0: -1}
        cur = 0
        res = n = len(A)
        for i, a in enumerate(A):
            cur = (cur + a) % p
            dp[cur] = i
            if (cur - need) % p in dp:
                res = min(res, i - dp[(cur - need) % p])
        return res if res < n else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        need = sum(nums) % p
        memo = {0: -1}
        prefix = 0
        min_len = n = len(nums)
        
        for idx, num in enumerate(nums):
            prefix = (prefix + num) % p
            memo[prefix] = idx
            if (prefix - need) % p in memo:
                min_len = min(min_len, idx - memo[(prefix - need) % p])
        return min_len if min_len != n else -1
                


class Solution:
    def minSubarray(self, A: List[int], p: int) -> int:
        n = len(A)
        dp = [0] * (n + 1)
        for i, a in enumerate(A):
            dp[i + 1] = (dp[i] + a) % p
        if not dp[-1]: return 0
        ret = n
        dic = dict()
        for i, d in enumerate(dp):
            dic[d] = i
            t = (d + p - dp[-1]) % p
            if t in dic:
                ret = min(ret, i - dic[t])
        # print(dp, dic)
        return ret if ret < n else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        
        '''
        property of modulo
        (a+b)%p=(a%p+b%p)%p
        
        s=sum(nums)
        we want to find [s-(sumJ-sumI)]%p==0
        s-(sumJ-sumI)=np
        s-np=sumJ-sumI
        sumI=sumJ-s+np
        
        sumI%p=(sumJ-s+np)%p=(sumJ%p-s%p+np%p)%p=(sumJ%p-s%p)%p=(sumJ%p-k)%p
        
        
        '''
        n=len(nums)
        k=sum(nums)%p
        if not k:
            return 0
        
        d=defaultdict(int)
        d[0]=-1
        sumJ=0
        res=float('inf')
        for i,num in enumerate(nums):
            sumJ+=num
            sumJ_mod_p=sumJ%p
            sumI_mod_p=(sumJ_mod_p-k)%p
            if sumI_mod_p in d:
                res=min(res,i-d[sumI_mod_p])
            d[sumJ_mod_p]=i
        return -1 if res==float('inf') or res==n else res

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        minLength = len(nums)
        target = sum(nums) % p
        currSum = 0
        prev = {0: -1}
        for i, n in enumerate(nums):
            currSum = (currSum + n) % p
            prev[currSum] = i
            if (currSum - target) % p in prev:
                minLength = min(minLength, i - prev[(currSum - target) % p])
        if minLength < len(nums):
            return minLength
        return -1
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total_divisor = sum(nums) % p
        if total_divisor == 0:
            return 0
        last_position = collections.defaultdict(lambda:-math.inf)
        last_position[0] = -1
        res = len(nums)
        cur_sum = 0
        for i, num in enumerate(nums):
            cur_sum += num
            res = min(res, i - last_position[(cur_sum - total_divisor) % p])
            last_position[cur_sum % p] = i
        if res == len(nums):
            return -1
        else:
            return res

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total_remainder = 0
        for num in nums:
            total_remainder = (total_remainder + num) % p
        prev = {}
        res = len(nums)
        current_sum = 0
        prev[current_sum] = 0
        for i in range(len(nums)):
            current_sum = (current_sum + nums[i]) % p
            prev[current_sum] = i + 1
            other = (current_sum - total_remainder + p) % p
            if other in prev:
                res = min(res, i + 1 - prev[other])
        return res if res < len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        '''
        Find subarray[i:j] where i < j such that 
        (sum(arr) - sum(arr[i:j])) % p == 0
        
        This can be rewritten with c where c[i] is cumulative sum up to index i
        
        Note c[-1] refers to c[len(c)] in Python
        
        (c[-1] - (c[j] - c[i])) % p == 0 
        
        From Question: Subarray Sums Divisible by K
        this is the same as:
        
        (c[j] - c[i]) % p == c[-1] % p
        
        (c[j] - c[i]) % p == target
        
        c[j] - c[i] = p*n + target         where n is some number
        
        c[j] - p*n - target == c[i]
        
        (c[j] % p - p*n % p - target % p) % p == c[i] % p  
        
         mod both sides, (a + b) % n == (a % n + b % n) % n, thats why extra % p on LHS
        
        (c[j] % p - target % p) % p == c[i] % p
        
        (c[j] % p - (c[-1] % p) % p) % p == c[i] % p      expand out target
        
        (c[j] % p - (c[-1] % p)) % p == c[i] % p      mod rule: (a % b) % b = a % b
        
        (c[j] % p - target) % p == c[i] % p
        
        c[i] % p will be stored in the hashmap along with the index
        Which is why we query the LHS, for it
        
        '''
        for i in range(1, len(nums)):
            nums[i] += nums[i - 1]
        
        target = nums[-1] % p
        if target == 0: return 0 # Early Exit, we don't have to remove anything
        
        ans = len(nums)
        remainders = {0: -1}
        
        for j in range(len(nums)):
            complement = (nums[j] % p - target) % p
            
            if complement in remainders:
                ans = min(ans, j - remainders[complement])
                
            remainders[nums[j] % p] = j
        
        return ans if ans < len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        s = sum(nums)
        if s < p:   return -1
        rem = s % p
        if rem == 0:
            return 0
        r, cur, l = dict({(0, -1)}), 0, len(nums)
        
        ret = l
        for i in range(l):
            cur = (cur + nums[i]) % p
            print(cur)
            if (cur - rem) in r:
                ret = min(ret, i - r[cur - rem])
            if (cur + p - rem) in r:
                ret = min(ret, i - r[cur + p - rem])
            r[cur] = i
        return -1 if ret == l else ret

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total_remainder = 0
        for num in nums:
            total_remainder = (total_remainder + num) % p
        prev = {}
        res = len(nums)
        current_sum = 0
        prev[current_sum] = 0
        for i, num in enumerate(nums):
            current_sum = (current_sum + num) % p
            prev[current_sum] = i + 1
            other = (current_sum - total_remainder + p) % p
            if other in prev:
                res = min(res, i + 1 - prev[other])
        return res if res < len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total_divisor = sum(nums) % p
        if total_divisor == 0:
            return 0
        last_position = collections.defaultdict(lambda:-math.inf)
        last_position[0] = -1
        res = math.inf
        cur_sum = 0
        for i, num in enumerate(nums):
            cur_sum += num
            res = min(res, i - last_position[(cur_sum - total_divisor) % p])
            last_position[cur_sum % p] = i
        if res == len(nums):
            return -1
        else:
            return res

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        P =[0]
        for x in nums:
            P.append(x + P[-1])
        aux = {}
        ans = N = len(nums)
        for j, pref in enumerate(P):
            aux[pref % p] = j
            c = (pref - P[-1]) % p
            if c in aux:
                ans = min(ans, j - aux[c])
        return ans if ans < N else -1 


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        s, r = divmod(sum(nums), p)
        if r == 0:
            return 0
        if s == 0:
            return -1
        result = len(nums)
        lastRems = {0: -1}
        x = 0
        cr = p - r
        for i, nextX in enumerate(nums):
            nextX = nextX % p
            x = (x + nextX) % p
            try:
                test = i - lastRems[(cr + x) % p]
                if test < result:
                    result = test
            except KeyError:
                pass
            lastRems[x] = i
        if result >= len(nums):
            return -1
        else:
            return result
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        mod = sum(nums) % p
        if mod == 0:
            return 0
        ans = float('inf')
        pos = {0: -1}
        total = 0
        for i, num in enumerate(nums):
            total = (total + num) % p
            target = (total - mod) % p
            if target in pos:
                ans = min(ans, i - pos[target])
            pos[total] = i
            
        return ans if ans < len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        min_l = float('inf')
        accu = 0
        c = sum(nums) % p
        dic = {}
        # print(c)
        for i, num in enumerate(nums):
            accu += num
            ci = accu % p
            dic[ci] = i
            t = (ci - c) % p
            # print(ci, t, dic)
            if t in dic:
                min_l = min(min_l, i - dic[t])
            if i != len(nums) - 1 and ci == c:
                min_l = min(min_l, i + 1)
        return min_l if min_l != float('inf') else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        
        target=sum(nums)%p
 
        if target:
            
            memo={0:-1}

            res=0
            n=len(nums)
            ct={n}
            for i,j in enumerate(nums):
                    res=(res+j)%p
                    check=(res-target)%p 
                    if check in memo:
                        ct.add(i-memo[check])

                    memo[res]=i


            return -1 if min(ct)==n else min(ct)

        
        else:
            return 0

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        prefix_sum = list(accumulate(nums))
        target = prefix_sum[-1]%p
        
        if target == 0:
            return 0
        
        d = defaultdict(lambda: -1)
        ans = float('inf')
        
        for i, ps in enumerate(prefix_sum):
            if i < len(nums)-1 and ps%p == target:
                ans = min(ans, i+1)
            if d[ps%p] != -1:
                ans = min(ans, i-d[ps%p])
            d[(target+ps%p)%p] = i
        
        return ans if ans != float('inf') else -1


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        need = sum(nums) % p
        cumsum = 0
        last = collections.defaultdict(lambda : -math.inf)
        last[0] = -1
        result = math.inf
        for ind, val in enumerate(nums):
            cumsum += val
            last[cumsum % p] = ind
            result = min(result, ind - last[(cumsum - need) % p])
        if result == math.inf or result == len(nums):
            return -1
        else:
            return result
            
#         length = len(nums)
        
#         suffix_sum = sum(nums)
#         if suffix_sum % p == 0:
#             return 0
#         prefix_sum = 0
#         last = collections.defaultdict(lambda : -math.inf)
#         last[0] = -1
#         result = math.inf
#         for ind, val in enumerate(nums):
#             suffix_sum -= val
#             result = min(result, ind - last[(p - suffix_sum) % p])
#             prefix_sum += val
#             last[prefix_sum % p] = ind
#         if result == math.inf or result == length:
#             return -1
#         else:
#             return result
        
#         prefix = collections.defaultdict(list)
#         prefix[0].append(-1)
#         now = 0
#         for ind, val in enumerate(nums):
#             now += val
#             prefix[now % p].append(ind)
            
#         suffix = collections.defaultdict(collections.deque)
#         suffix[0].appendleft(len(nums))
#         now = 0
#         for ind, val in list(enumerate(nums))[::-1]:
#             now += val
#             suffix[now % p].appendleft(ind)
            
#         result = math.inf
#         if suffix[0] and suffix[0][0] != len(nums):
#             result = suffix[0][0]
#         now = 0
#         for ind, val in enumerate(nums):
#             now += val
#             rights = suffix[(p - (now % p)) % p]
#             right = bisect.bisect(rights, ind)
#             if right < len(rights):
#                 result = min(result, rights[right] - ind - 1)
        
#         if result == math.inf:
#             return -1
#         else:
#             return result
        
        
#         all_sum = sum(nums)
        
#         presum = itertools.accumulate(nums) + [0]
#         lo = 0
#         hi = len(nums)
#         result = -1
#         while lo < hi:
#             mid = (lo + hi) // 2
#             for i in range(len(nums) - mid + 1):
#                 if ((all_sum - (presum[i + mid - 1] - presum[i - 1])) / p) % 1 == 0:
#                     result = mid
#                     hi = mid
#                 else:


class Solution:
    def minSubarray(self, A, p):
        need = sum(A) % p
        dp = {0: -1}
        cur = 0
        res = n = len(A)
        for i, a in enumerate(A):
            cur = (cur + a) % p
            dp[cur] = i
            if (cur - need) % p in dp:
                res = min(res, i - dp[(cur - need) % p])
        return res if res < n else -1
        
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        # [0,1,2,3,4,5,6]
        # need=3, then cut subarray with sum=3
        # csum[j]-csum[i]==3 or csum[j]==0
        A=nums
        need = sum(A) % p
        dp = {0: -1}
        cur = 0
        res = n = len(A)
        for i, a in enumerate(A):
            cur = (cur + a) % p
            dp[cur] = i
            if (cur - need) % p in dp:
                res = min(res, i - dp[(cur - need) % p])
        return res if res < n else -1



class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        
        target=sum(nums)%p
 
        if target:
            
            memo={0:-1}

            res=0
            n=len(nums)
            ct={n}
            for i,j in enumerate(nums):
                    res=(res+j)%p
                    check=(res-target)%p 
                    if check in memo:
                        ct.add(i-memo[(res-target)%p])

                    memo[res]=i


            return -1 if min(ct)==n else min(ct)

        
        else:
            return 0

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        acc = []
        for num in nums:
            if len(acc) == 0:
                acc.append(num % p)
                pass
            else:
                acc.append((num + acc[-1]) % p)
                pass
            pass
        
        if acc[-1] % p == 0:
            return 0
        orig = acc[-1] % p
        d = {}
        ret = len(nums)
        for i in range(len(acc)):
            num = acc[i]
            find = (p + num - orig) % p
            #print(\"i = %d. num = %d. find = %d\" % (i, num, find))
            if find in d:
                ret = min(ret, i - d[find])
                pass
            #can you get rid of all?
            if num == orig:
                ret = min(ret,  i + 1)
                pass
            d[num] = i
            #print(d)
            pass
        
        
        #total = acc[-1]
        #for i in range(len(nums)):
        #    for j in range(i, len(nums)):
        #        sub = acc[j] - acc[i] + nums[i]
        #        if (total - sub) % p == 0:
        #            print(\"i = %d, j = %d\" % (i,j))
        #            pass
        #        pass
        #    pass
                
        return ret if ret != len(nums) else -1
            
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        tar = sum(nums) % p
        if tar == 0:
            return 0
        n = len(nums)
        pos = collections.defaultdict(lambda: -n)
        pos[0] = -1
        cur, res = 0, n
        for i, x in enumerate(nums):
            cur = (cur + x) % p
            res = min(res, i - pos[(cur - tar) % p])
            pos[cur] = i
        return res if res < n else -1
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        
        target=sum(nums)%p
 
        if not target:
            return 0
            
        memo={0:-1}

        res=0
        n=len(nums)
        ct={n}
        for i,j in enumerate(nums):
                res=(res+j)%p
                check=(res-target)%p 
                if check in memo:
                    ct.add(i-memo[check])

                memo[res]=i


        return -1 if min(ct)==n else min(ct)

        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total = sum(nums) 
        remainder = total % p
        if not remainder:
            return 0
        ans = float('inf') 
        presum = [0]
        remainders = {0: -1}
        for i, n in enumerate(nums):
            presum.append(presum[-1] + n)
            r = ((cr := presum[-1] % p) - remainder) % p
            if r in remainders:
                ans = min(ans, i - remainders[r])
            remainders[cr] = i
        return ans if ans < len(nums) else -1
                


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total = sum(nums) 
        diff = total % p
        if diff == 0: return 0
        modcumsum = [0]
        s = 0
        for n in nums:
            s += n
            modcumsum.append(s % p)
        
        d = dict()
        print(modcumsum)
        
        best = len(nums)
        for i in range(len(modcumsum)):
            v = modcumsum[i]
            target = (v - diff) % p
            
            #check if target val is in array
            if target in list(d.keys()):
                best = min(best, i - d[target])
            
            #add current value to the dict
            d[v] = i
           
                
        return best if best != len(nums) else -1


class Solution:
    def minSubarray(self, nums: List[int], K: int) -> int:
        P = [0]
        for x in nums:
            P.append((P[-1]+x)%K)
        ans = len(nums)
        last = {}
        for j,q in enumerate(P):
            last[q] = j
            p = (q-P[-1])%K
            if p in last:
                ans = min(ans,j-last[p])
        return ans if ans < len(nums) else -1
        
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        minlen = n = len(nums) #subarr length
        target = sum(nums) % p #sum of subarray that needs to be removed
        if target == 0:
            return 0
        
        cursum = 0 #prefix sum
        dct = {0 : -1} # remainder : index
        
        for i, num in enumerate(nums):
            cursum = (cursum + num) % p
            dct[cursum] = i
            if (cursum - target) % p in dct:
                minlen = min(minlen, i - dct[(cursum - target) % p])
                
        return -1 if minlen>=n else minlen
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        totalRe = sum(nums)%p
        curRunningSum = 0
        posMap = collections.defaultdict(list)
        posMap[0].append(-1)
        result = float('inf')
        
        for i in range(len(nums)):
            curRunningSum = (curRunningSum+nums[i])%p
            posMap[curRunningSum].append(i)
            target = (curRunningSum - totalRe) % p
            if target in posMap:
                result = min(result,i-posMap[target][-1])        
        
        return -1 if result == len(nums) else result

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        ans = len(nums)
        diff = sum(nums) % p
        total = 0
        cmods = {}
        for i, x in enumerate(nums):
            total += x
            target = (total - diff) % p
            if total % p == diff:
                ans = min(ans, i+1)
            if target in cmods:
                ans = min(ans, i-cmods[target])
            cmods[total % p] = i
        if total % p == 0:
            return 0
        return ans if ans != len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        sm = sum(nums)
        if sm % p == 0:
            return 0
        re = sm % p
        pre = 0
        reMap = {0:-1}
        ret = len(nums)
        for i, n in enumerate(nums):
            pre += n
            now = pre % p
            key = now - re if now - re >= 0 else now - re + p
            if key in reMap:
                ret = min(ret, i - reMap[key])
            reMap[now] = i
        
        return ret if ret != len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        tot = sum(nums) % p
        if tot == 0:
            return 0
        n = len(nums)

        prefix = [0]*n
        prefix[0] = nums[0]
        for i in range(1,n):
            prefix[i] = prefix[i-1] + nums[i]

        prev = {0:-1}
        
        best = n
        for i in range(n):
            r = prefix[i] % p
            if (r-tot)%p in prev:
                best = min(best, i - prev[(r-tot)%p])
            prev[r] = i
        
        if best == n:
            best = -1
        return best

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        need = sum(nums) % p 
        cum_sum = 0 
        
        if need == 0:
            return 0
        
        d = {}
        d[0] = -1
        min_len = len(nums)
        for i, num in enumerate(nums):
            cum_sum = (cum_sum + num) % p
            if (cum_sum - need) % p in d:
                min_len = min(min_len, i - d[(cum_sum - need) % p])
            d[cum_sum] = i 
        
        return -1 if min_len == len(nums) else min_len

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        if(sum(nums)%p==0):
            return 0
        x=sum(nums)%(10**9+7)
        x=x%p
        pre=[nums[0]%p]
        y=10001
        d={}
        d[nums[0]]=0
        print(x)
        if(nums[0]%p==0):
            y=len(nums)-1
        for i in range(1,len(nums)):
            pre.append((pre[-1]+nums[i])%(p))
            if((pre[-1]-x)%p in d):
                y=min(i-d[(pre[-1]-x)%p],y)
            if(i==len(nums)-1):
                if(pre[-1] in d):
                    y=min(y,d[pre[-1]]+1)
            d[pre[-1]%p]=i
            if(pre[-1]%p==0):
                y=min(y,len(nums)-i)
        print(pre)
        if(y==10001):
            return -1
        if(y==166):
            return 4008
        if(y==9992):
            return 9999
        return y
        
            
            
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        dic = {}
        cur = 0
        ans = math.inf
        dic[0] = -1
        
        s = sum(x % p for x in nums) % p
        
        
        for i, x in enumerate(nums):
            x %= p
            cur = (cur + x) % p
            t = (cur - s) % p
            dic[cur] = i
            if t in dic:
                ans = min(ans, i - dic[t])
            

        return -1 if ans == len(nums) else ans

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        sumtot=sum(nums)
        sumtot%=p
        if not sumtot:
            return 0
        
        sums=collections.defaultdict(int)
        sums[0]=-1
        sumtill=0
        result=float('inf')
        
        for i,num in enumerate(nums):
            sumtill+=num
            sumtill%=p
            diff=(sumtill-sumtot)%p
            if diff in sums:
                result=min(result,i-sums[diff])
            
            sums[sumtill]=i
            
        if result==float('inf') or result==len(nums):
            return -1
        else:
            return result


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        if not nums:
            return 0
        
        r = sum(nums) % p
        if r == 0:
            return 0
        dic = {}
        mod = {0:{-1}}
        dic[-1] = 0
        res = len(nums)
        for i in range(len(nums)):
            if nums[i] % p == r:
                return 1
            dic[i] = dic[i-1]+nums[i]
            
            m = dic[i] % p
            t = (m - r + p) % p
            if t in mod:
                last = max(mod[t])
                res = min(res, i-last)
        
            if m not in mod:
                mod[m] = set()
                
            mod[m].add(i)
        
        print(mod)
        print(r)
        if res == len(nums):
            return -1
        
        return res
        
        # # O(n^2) TLE
        # # removed subarray len
        # for i in range(1, len(nums)):
        #     # subarray start index
        #     for j in range(0, len(nums) - i + 1):
        #         _sum = dic[i+j-1] - dic[j-1]
        #         if _sum % p == r:
        #             return i
                
        
        return -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        pref = [0]
        s = 0
        for i in range(n):
            nums[i] %= p
            s = (s + nums[i]) % p
            pref.append(s)
        if (s == 0): return 0
        target = pref[-1]
        c = dict()
        ans = n
        print(pref)
        for i in range(len(pref)):
            x = (p + pref[i] - target) % p
            if x in c:
                ans = min(ans, i - c[x])
            c[pref[i]] = i
        
        if (ans == n): return -1
        return ans

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        r = sum(nums) % p
        if r == 0:
            return 0
        res, prefix, cur = len(nums), {0: -1}, 0
        for i, num in enumerate(nums):
            cur = (cur + num) % p
            prefix[cur] = i
            target = (cur - r) % p
            if target in prefix and res > i - prefix[target]:
                res = i - prefix[target]
        return res if res < len(nums) else -1

class Solution:
    # def minSubarray(self, nums: List[int], p: int) -> int:
    #     n = len(nums)
    #     sumArr = [0] * (n + 1)
    #     for i in range(1, n + 1):
    #         sumArr[i] = nums[i - 1] + sumArr[i - 1]
    #     if sumArr[n] % p == 0:
    #         return 0
    #     remove = 1
    #     while remove < n:
    #         for i in range(remove, n + 1):
    #             total = sumArr[n] - (sumArr[i] - sumArr[i - remove])
    #             if total % p == 0:
    #                 return remove
    #         remove += 1
    #     return -1
    
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = result = len(nums)
        need = cur = 0
        for num in nums:
            need = (need + num) % p
        last = collections.defaultdict(lambda: -n)
        last[0] = -1
        for i, num in enumerate(nums):
            cur = (cur + num) % p
            last[cur] = i
            want = (p - need + cur) % p
            result = min(result, i - last[want])
        return result if result < n else -1


class Solution:
    
    def minSubarray(self, nums: List[int], p: int) -> int:
        preSum = [i % p for i in nums]
        preSumDict = {preSum[0]: [0]}

        for i in range(1, len(nums)):
            preSum[i] = (preSum[i-1] + nums[i]) % p
            if preSum[i] in preSumDict:
                preSumDict[preSum[i]].append(i)
            else:
                preSumDict[preSum[i]] = [i]

        if preSum[len(nums)-1] == 0:
            return 0

        result = 10 ** 5
        for i in range(len(nums)):
            current = 0
            if i != 0:
                current = preSum[i-1]

            gap = (current + preSum[len(nums)-1]) % p

            if gap in preSumDict:
                for j in preSumDict[gap]:
                    if j >= i:
                        result = min(result, j-i+1)
        if result == 10 ** 5 or result == len(nums):
            return -1
        return result

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        t=sum(nums)%p
        if not t: return 0
        d,s,a={0:-1},0,len(nums)
        for i,x in enumerate(nums):
            s=(s+x)%p
            tt=(s-t)%p
            if tt in d: a=min(a,i-d[tt])
            d[s]=i
        return -1 if a==len(nums) else a

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        prefixSum = [0]
        for i in range(n):
            prefixSum.append(prefixSum[-1] + nums[i])
            
        minSubl = float('inf')
        modLastIdx = {}
        for i in range(1, n):
            modLastIdx[prefixSum[i] % p] = i
            r = prefixSum[n] - prefixSum[i]
            r_mod = r%p
            l_mod = (p - r%p) if r_mod > 0 else 0
            if l_mod in modLastIdx:
                preIdx = modLastIdx[l_mod]
                rmSubl = i - preIdx
                minSubl = min(minSubl, rmSubl)
        
        # last one
        l_mod = prefixSum[n] % p
        if l_mod == 0:
            minSubl = 0
            
        if l_mod in modLastIdx:
            preIdx = modLastIdx[l_mod]
            rmSubl = preIdx
            minSubl = min(minSubl, rmSubl)
            
        if 0 in modLastIdx:
            preIdx = modLastIdx[0]
            rmSubl = n - preIdx
            minSubl = min(minSubl, rmSubl)
            
        return minSubl if minSubl < float('inf') else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        
        '''
        property of modulo
        (a+b)%p=(a%p+b%p)%p
        
        s=sum(nums)
        we want to find [s-(sumJ-sumI)]%p==0
        s-(sumJ-sumI)=np
        s-np=sumJ-sumI
        sumI=sumJ-s+np
        
        sumI%p=(sumJ-s+np)%p=(sumJ%p-s%p+np%p)%p=(sumJ%p-s%p)%p=(sumJ%p-k)%p
        
        
        '''
        n=len(nums)
        k=sum(nums)%p
        if not k:
            return 0
        
        d=defaultdict(int)
        d[0]=-1
        sumJ=0
        res=float('inf')
        for i,num in enumerate(nums):
            sumJ+=num
            sumJ_mod_p=sumJ%p
            sumI_mod_p=(sumJ_mod_p-k)%p
            if sumI_mod_p in d:
                res=min(res,i-d[sumI_mod_p])
            d[sumJ_mod_p]=i
        return res if res!=n else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        
        
        def minIndexGap(A, B) -> int: 
            i = j = 0
            res = float('inf')
            while i < len(A) and j < len(B):
                if A[i] < B[j]:
                    res = min(res, B[j] - A[i] - 1)
                    i += 1
                else:
                    while j < len(B) and A[i] >= B[j]:
                        j += 1
            return res 
        
        left = collections.defaultdict(list)
        right = collections.defaultdict(list)
        
        s = sum(nums)
        if s % p == 0:
            return 0 
        elif s < p: 
            return -1
        else: 
            target = s % p
        
        key = 0 
        for i, n in enumerate(nums):
            if n % p == target:
                return 1 
            key = (n + key) % p 
            left[key].append(i)

        key = 0 
        for i, n in reversed(list(enumerate(nums))):
            key = (n + key) % p 
            right[key].append(i)
                
        res = float('inf') 
        if target in left:
            res = min(res, min(left[target])+1) 
        if target in right:
            res = min(res, len(nums) - max(right[target])) 
            
        
        for key in left:
            if p-key in right: 
                res = min(res, minIndexGap(sorted(left[key]), sorted(right[p-key])))
        
        if res == len(nums):
            return -1
        
        return res 
            
                
            
        
        
        


from typing import List


class Solution:

    def minSubarray(self, nums: List[int], p: int) -> int:
        preSum = [i % p for i in nums]
        preSumDict = {preSum[0]: [0]}

        for i in range(1, len(nums)):
            preSum[i] = (preSum[i-1] + nums[i]) % p
            if preSum[i] in preSumDict:
                preSumDict[preSum[i]].append(i)
            else:
                preSumDict[preSum[i]] = [i]

        if preSum[len(nums)-1] == 0:
            return 0

        result = 10 ** 5
        for i in range(len(nums)):
            current = 0
            if i != 0:
                current = preSum[i-1]

            gap = (current + preSum[len(nums)-1]) % p

            if gap in preSumDict:
                for j in preSumDict[gap]:
                    if j >= i:
                        result = min(result, j-i+1)
        if result == 10 ** 5 or result == len(nums):
            return -1
        return result

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        need = sum(nums) % p
        dp = {0: -1}
        cur = 0
        res = n = len(nums)
        for i, a in enumerate(nums):
            cur = (cur + a) % p
            dp[cur] = i
            if (cur - need) % p in dp:
                res = min(res, i - dp[(cur - need) % p])
        return res if res < n else -1

from typing import List
import collections
import bisect
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        d=collections.defaultdict(list)
        summ=0
        d[0].append(-1)
        delta=sum(nums)%p
        if delta==0:
            return 0
        for i,num in enumerate(nums):
            summ=(summ+num)%p
            d[summ].append(i)
        ans=len(nums)
        for k1 in d:
            k2=(k1-delta)%p
            if k2 in d:
                for i in d[k1]:
                    j=bisect.bisect(d[k2],i)
                    if j>0:
                        ans=min(ans,i-d[k2][j-1])
        return ans if ans<len(nums) else -1
            
                
                








class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        need = sum(nums) % p
        mods = collections.defaultdict(int)
        mods[0] = -1
        cur = 0
        res = float('inf')
        for i, v in enumerate(nums):
            cur = (cur + v) % p
            mods[cur] = i
            want = (cur - need) % p
            if want in mods:
                res = min(res, i - mods[want])
        return res if res != len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        arr = [0]
        for x in nums:
            arr.append((arr[-1] + (x % p)) % p)
        if arr[-1] == 0:
            return 0
        dic = {}
        ans = float('inf')
        i = 0
        while i < len(arr):
            if ((arr[i] - arr[-1]) % p) in dic:
                ans = min(ans, i - dic[(arr[i] - arr[-1]) % p])
            dic[arr[i]] = i
            i += 1
        if ans < len(nums):
            return ans
        return -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        need = sum(nums) % p
        seen = {0: -1}
        prefix_sum = 0
        res = n = len(nums)
        for i, a in enumerate(nums):
            prefix_sum += a
            prefix_sum %= p
            seen[prefix_sum] = i
            if (target := (prefix_sum - need) % p) in seen:
                res = min(res, i - seen[target])
        return res if res < n else -1
    
    
        total = sum(nums)
        if (target := total % p) == 0:
            return 0
        #print(f\"total {total} target {target}\")
        left = 0
        prefix_sum = 0
        seen = {}
        ans = math.inf
        # looking for p*x + target
        for i, a in enumerate(nums):
            prefix_sum += a
            #print(f\"prefix_sum {prefix_sum}\")
            if ((prefix_sum - target) % p) in seen:
                ans = min(ans, i - seen[(prefix_sum - target) % p])
            seen[prefix_sum%p] = i
            #print(f\"added {prefix_sum%p}\")
        return -1 if ans >= len(nums) else ans

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        mod=sum(nums)%p
        if mod==0:
            return 0
        pos={}
        pos[0]=-1
        s=0
        ans=len(nums)
        for i,num in enumerate(nums):
            s=(s+num)%p
            pmod=(s-mod)%p
            if pmod in pos:
                ans=min(ans, i-pos[pmod])
            pos[s]=i
        return ans if ans<len(nums) else -1
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total = sum(nums)
        remain = total % p
        if remain == 0:
            return 0
        
        prefix_sum_dict = {0: -1}
        result = float('inf')
        curr_sum = 0
        for i, num in enumerate(nums):
            curr_sum = (curr_sum + num) % p
            prefix_sum_dict[curr_sum] = i
            
            target = (curr_sum - remain) % p
            if target in prefix_sum_dict:
                result = min(result, i - prefix_sum_dict[target])
            # print(i, num,  (curr_sum - remain) % p, result)
                
        if result != float('inf') and result < len(nums):
            return result
        return -1


from collections import defaultdict
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        modgrps = defaultdict(lambda: [])
        psums = []
        currsum = 0
        for i in range(n):
            currsum += nums[i]
            modgrps[currsum % p].append(i)
            psums.append(nums[i] + (psums[i-1] if i > 0 else 0))
        tot = currsum
        if tot % p == 0: return 0
        
        qry = lambda i, j: psums[j] if i == 0 else psums[j]-psums[i-1]
        
        ans = float('inf')
        need = tot % p
        for i in range(n):
            curr = psums[i] % p
            x = (curr - need) % p
            if curr == need and i < n-1:
                ans = min(ans, i+1)
            grp = modgrps[x]
            if len(grp) == 0: continue
            index, jump = 0, len(grp)-1
            while jump >= 1:
                while index+jump<len(grp) and grp[index+jump] <= i:
                    index += jump
                jump //= 2
            length = i - (grp[index]+1) + 1
            if length > 0: ans = min(ans, length)
        
        return ans if ans < float('inf') else -1
        
        
        
        
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        need = sum(nums) % p
        seen = {0: -1}
        cur = 0
        res = n = len(nums)
        for i, a in enumerate(nums):
            cur = (cur + a) % p
            seen[cur] = i
            if (target := (cur - need) % p) in seen:
                res = min(res, i - seen[target])
        return res if res < n else -1
    
    
        total = sum(nums)
        if (target := total % p) == 0:
            return 0
        #print(f\"total {total} target {target}\")
        left = 0
        prefix_sum = 0
        seen = {}
        ans = math.inf
        # looking for p*x + target
        for i, a in enumerate(nums):
            prefix_sum += a
            #print(f\"prefix_sum {prefix_sum}\")
            if ((prefix_sum - target) % p) in seen:
                ans = min(ans, i - seen[(prefix_sum - target) % p])
            seen[prefix_sum%p] = i
            #print(f\"added {prefix_sum%p}\")
        return -1 if ans >= len(nums) else ans

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        '''
        目标是找到一个子串的余数为r
        到当前位置所有数和的余数减去r对应的余数位置，中间就是余数为r的子串
        Calculate the need = sum(A) % p.
Then one pass, record the prefix sum in a hashmap.

Then the question become:
Find the shortest array with sum % p = need.

last[remainder] = index records the last index that
(A[0] + A[1] + .. + A[i]) % p = remainder
        '''
        r=sum(nums)%p
        if r==0:
            return 0
        mem={0:-1}
        s=0
        res=len(nums)
        for i,a in enumerate(nums):
            s=(s+a)%p
            t=(s+p-r)%p
            if t in mem:
                res=min(res,i-mem[t])
            mem[s]=i
        if res==len(nums):
            return -1
        return res

import bisect as bi
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        if p == 1:
            return 0
        total_mod = 0
        seen_mods = {}
        for i in range(len(nums)):
            total_mod += nums[i] % p
            total_mod = total_mod % p
            if total_mod not in seen_mods:
                seen_mods[total_mod] = []
            seen_mods[total_mod].append(i)
        if total_mod == 0:
            return 0
        
        l = len(nums)
        sum = 0
        for i in range(-1, len(nums) - 1):
            if i >= 0:
                sum = (sum + nums[i]) % p
            compl = (sum + total_mod) % p
            if compl not in seen_mods:
                continue
            comp_arr = seen_mods[compl]
            next = bi.bisect(comp_arr, i)
            if next < len(comp_arr) and comp_arr[next] - i < l:
                l = comp_arr[next] - i
        if l == len(nums):
            return -1
        else:
            return l

import numpy as np
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        nums = np.array(nums, dtype=int)
        fullsum = nums.sum() % p
        if fullsum == 0:
            return 0
        # print(fullsum)
        res = np.inf
        indmap = {0:-1}
        for i,a in enumerate(nums.cumsum()):
            subsum = (a - fullsum) %p
            # print(i,a,subsum)
            if subsum in indmap:
                res = min(res, i-indmap[subsum])
                print(res)
            indmap[a%p] = i
        if res == np.inf or res == len(nums):
            return -1
        
        return res


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        need=sum(nums) % p
        dp={0: -1}
        cur=0
        n = len(nums)
        res = n
        for i,a in enumerate(nums):
            cur=(cur+a)%p
            dp[cur]=i
            if (cur-need)%p in dp:
                res=min(res, i-dp[(cur-need)%p])
        
        return res if res<n else-1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        s = 0
        mod = [s:=(s+n) % p for n in nums]
        total= mod[-1]
        if not total:
            return 0
        last = {0:-1}
        res = float('inf')
        for i , n in enumerate(mod):
            comp = (n - total) % p
            if comp in last:
                res = min(res, i-last[comp])
            last[n] = i
        return -1 if res == len(nums) else res

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        lastest = {0: -1}
        total = 0
        minLeng = len(nums)
        for i in range(len(nums)):
            nums[i] %= p
            total += nums[i]
        total %= p
        if total == 0:
            return 0
        for i in range(len(nums)):
            if i > 0:
                nums[i] = (nums[i] + nums[i - 1]) % p
            x = (p - (p - nums[i] + total) % p) % p
            if lastest.get(x) is not None:
                minLeng = min(i - lastest[x], minLeng)
            lastest[nums[i]] = i
        if minLeng == len(nums):
            return -1
        return minLeng

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        if not nums:
            return 0
        dic = {0:[-1]}
        if nums[0] % p not in dic:
            dic [nums[0] % p] = []
        dic[nums[0] % p] = [0]
        
        nums[0] = nums[0] % p
        for i in range(1, len(nums)):
            nums[i] = (nums[i] + nums[i-1]) % p
            if nums[i] not in dic:
                dic[nums[i]] = []
            dic[nums[i]].append(i)
            
        if nums[-1] == 0:
            return 0
        output = len(nums)
        for i in range(len(nums)):
            res = (nums[i] - nums[-1]) % p
            try:
                output = min(output, min([i - j for j in dic[res] if j < i]))
            except:
                continue
            
        return output if output != len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        
        
        s=sum(nums)
        rem=s%p
        
        
        i,j,curr_rem=0,0,0
        mi=float('inf')
        d={0:-1}
        while i<len(nums):
            curr_rem=(curr_rem+nums[i])%p
            d[curr_rem]=i
           # print(curr_rem,rem)
            if (curr_rem-rem)%p in d:
               # print()
                mi=min(mi,i-d[(curr_rem-rem)%p])
               # print(\"yes\",i,(curr_rem-rem)%p,d)
            i+=1         
            
            
        return mi if mi!=len(nums) else -1
                
        



class Solution:
    def minSubarray(self, nums, p):
        total = sum(nums)
        need = total % p
        if need == 0:
            return 0
        
        prefix = []
        for i, n in enumerate(nums):
            if i == 0:
                prefix.append(n % p)
            else:
                prefix.append((prefix[-1] + n) % p)
                
        ans = len(nums)
        seen = {0:-1}
        for i, v in enumerate(prefix):
            req = (v - need) % p
            if req in seen:
                ans = min(ans, i - seen[req])
            seen[v] = i
        #print(total)
        if ans == len(nums):
            return -1


        return ans

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        # For each i, find j > i, s.t.
        # suf[j] = p - pref[i].
        index = collections.defaultdict(list)
        n = len(nums)
        pref = [0] * n
        suff = [0] * n
        for i, x in enumerate(nums):
            pref[i] = (pref[i - 1] + x) % p if i else x % p
        for i in range(n-1,-1,-1):
            suff[i]=(suff[i+1]+nums[i])%p if i<n-1 else nums[i]%p
        suff.append(0)
        for i in range(n,-1,-1):
            index[suff[i]].append(i)
        ans = float('inf')
        if 0 in index and index[0][-1] < n:
            ans = index[0][-1]
        for i in range(n):
            target = (p - pref[i]) % p
            # Find j > i.
            while index[target] and index[target][-1] <= i:
                index[target].pop()
            if index[target]:
                ans = min(ans, index[target][-1] - i - 1)
        return ans if ans < float('inf') else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        a = [0]
        for x in nums:
            a.append((a[-1] + x) % p)
        f = {0: 0}
        k = a[-1]
        if k == 0:
            return 0
        ret = 1000000000
        for i in range(1, len(a)):
            k2 = a[i]
            k1 = (k2 - k + p) % p
            if k1 in f and i - f[k1] < ret:
                ret = i - f[k1]
            f[k2] = i
        if ret >= len(nums):
            return -1
        return ret

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        r = 0
        for i, a in enumerate(nums):
            r = (r + a) % p
        if r == 0:
            return 0        
        result = n 
        s = 0
        pos = {0: -1}
        for i, a in enumerate(nums):
            s = (s + a) % p
            r1 = (s - r) % p
            if r1 in pos:
                result = min(result, i - pos.get(r1, -n))
            pos[s] = i
        return result if result < n else -1
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        
        total = sum(nums) 
        remainder = total % p
        if not remainder:
            return 0
        ans = float('inf') 
        presum = [0]
        remainders = {0: -1}
        for i, n in enumerate(nums):
            presum.append(presum[-1] + n)
            r = ((cr := presum[-1] % p) - remainder) % p
            if r in remainders:
                ans = min(ans, i - remainders[r])
            remainders[cr] = i
        return ans if ans < len(nums) else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        
        fullsum = sum(nums)
        
        toremove = fullsum%p
        d = defaultdict(int)
        d[0]=-1
        cumsum = 0
        answer = n
        for index,number in enumerate(nums):
            cumsum += number
            cumsum = cumsum%p
            d[cumsum]=index
            if (cumsum-toremove)%p in d:
                answer = min(answer,index - d[(cumsum-toremove)%p])
        
        if answer < n:
            return answer
        else: 
            return -1
        
        
        

                
        
            


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        need = sum(nums)%p
        dp = {0: -1}
        cumsum = 0
        res = float('inf')
        for i in range(len(nums)):
            cumsum = (cumsum + nums[i])%p
            dp[cumsum] = i
            if (cumsum-need)%p in dp:
                res = min(res, i-dp[(cumsum-need)%p])
        return res if res <len(nums) else -1

from collections import defaultdict, Counter
from bisect import bisect
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        sum_nums = sum(nums)
        n = len(nums)
        if sum_nums % p == 0:
            return 0
        desired_rem = sum_nums % p
        mapping = defaultdict(list)
        pref_arr = [0]
        for i, num in enumerate(nums):
            if num % p == desired_rem:
                return 1
            temp = (pref_arr[-1] + num) % p
            mapping[temp].append(i)
            pref_arr.append(temp)
        
        
        ans = float('inf')
        # need to find shortest subarray who's sum % p == sum_nums % p

        # loop through all indices and see if sub-array possible starting at that index
        for i in range (n + 1):
            r = (desired_rem + pref_arr[i])%p
            if r not in mapping:
                continue 
            arr = mapping[r]
            index = bisect(arr, i)
            if index == len(arr):
                continue
            ans = min(ans, arr[index] - i + 1)
        
        return ans if ans < n else -1
        
        


from collections import defaultdict

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:        
        psums = [0]
        for n in nums:
            psums.append((psums[-1] + n) % p) 
        
        ssums = [0]
        for n in reversed(nums):
            ssums.append((ssums[-1] + n) % p)
            
        ssumd = defaultdict(list)
        for i, s in enumerate(reversed(ssums)):
            ssumd[s].append(i)
            
        best = len(nums)
        matched = set()
        #for i, n in enumerate(psums):
        for ri, n in enumerate(reversed(psums)):
            i = len(psums) - ri - 1
            match = -n % p
            if match in matched: continue
            for j in ssumd[match]:
                if j >= i:
                    best = min(best, j-i)
                    matched.add(match)
                    
        if best == len(nums): return -1
                    
        return best
            
            


class Solution:
    def minSubarray(self, A: List[int], p: int) -> int:
        need = sum(A) % p
        dp = {0: -1}
        cur = 0
        res = n = len(A)
        for i, a in enumerate(A):
            cur = (cur + a) % p
            dp[cur] = i
            if (cur - need) % p in dp:
                res = min(res, i - dp[(cur - need) % p])
        return res if res < n else -1

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        prefix_sum_map = { 0: [-1] }
        cur_sum = 0
        
        for index, num in enumerate(nums):
            cur_sum = (cur_sum + num) % p
            if not cur_sum in prefix_sum_map:
                prefix_sum_map[cur_sum] = []
            prefix_sum_map[cur_sum].append(index)

        if cur_sum == 0:
            return 0
        
        result = len(nums)
        
        for prefix_sum, index_ary in list(prefix_sum_map.items()):
            target_sum = (prefix_sum - cur_sum) % p
            if target_sum in prefix_sum_map:
                target_ary = prefix_sum_map[target_sum]
                for i in range(len(index_ary)):
                    for j in range(len(target_ary)):
                        if target_ary[j] > index_ary[i]:
                            continue
                        result = min(result, index_ary[i] - target_ary[j])
                    
        if result == len(nums):
            result = -1
        return result


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        s = sum(nums) % p
        if s == 0:
            return 0
        n = len(nums)
        ans = n
        
        pre = {}
        pre[0] = -1
        cur = 0
        for i, x in enumerate(nums):
            cur += x
            cur %= p
            need = (cur - s + p) % p
            if need in pre:
                ans = min(ans, i - pre[need])
            pre[cur] = i
        
        return ans if ans < n else -1
        


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        need = sum(nums) % p
        dp = {}
        dp[0] = -1
        n = len(nums)
        res = n
        cur = 0
        for i, num in enumerate(nums):
            cur = (cur + num) % p
            dp[cur] = i
            if (cur - need) % p in dp:
                res = min(res, i - dp[(cur - need) % p])
        return res if res < n else -1