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: MEDIUM
Tags: Data structures

Range queries
Skill types: Data structures

Range queries

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
			if (cur_rem - rem) % p in h_rem:
				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
			c = (p - (ss - s) % p) % p
			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:
		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
		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
			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])
		return ret if ret < n else -1


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:
		for i in range(1, len(nums)):
			nums[i] += nums[i - 1]
		target = nums[-1] % p
		if target == 0:
			return 0
		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:
		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:
		min_l = float('inf')
		accu = 0
		c = sum(nums) % p
		dic = {}
		for (i, num) in enumerate(nums):
			accu += num
			ci = accu % p
			dic[ci] = i
			t = (ci - c) % p
			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


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
			if find in d:
				ret = min(ret, i - d[find])
				pass
			if num == orig:
				ret = min(ret, i + 1)
				pass
			d[num] = i
			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:
		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
			if target in list(d.keys()):
				best = min(best, i - d[target])
			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)
		target = sum(nums) % p
		if target == 0:
			return 0
		cursum = 0
		dct = {0: -1}
		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
		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 = 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)
		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:

		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
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
		left = 0
		prefix_sum = 0
		seen = {}
		ans = math.inf
		for (i, a) in enumerate(nums):
			prefix_sum += a
			if (prefix_sum - target) % p in seen:
				ans = min(ans, i - seen[(prefix_sum - target) % p])
			seen[prefix_sum % p] = i
		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])
		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:
		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
		res = np.inf
		indmap = {0: -1}
		for (i, a) in enumerate(nums.cumsum()):
			subsum = (a - fullsum) % p
			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:
		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
			if (curr_rem - rem) % p in d:
				mi = min(mi, i - d[(curr_rem - rem) % p])
			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
		if ans == len(nums):
			return -1
		return ans


class Solution:

	def minSubarray(self, nums: List[int], p: int) -> int:
		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
			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:
		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')
		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 (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, 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