在Python中使总和可被P整除的程序

假设有一个数组nums和另一个值p，我们删除最小的子数组（而不是整个数组），使剩余值的总和可被p整除。如果没有这样的子数组，则找到我们需要删除的最小子数组的长度，否则返回-1。

因此，如果输入如下nums = [8,2,6,5,3] p = 7，则输出将为1，因为如果我们删除3，则总和将为21，可以被7整除。

要解决此问题，我们将遵循以下步骤 –

ans := infinity
s :=（nums中所有元素的总和）mod p
d := 包含键值对 {0：-1}的映射
cum := 0
如果s与0相同，则
- 返回0
对于i在0到nums的大小范围内，进行以下操作
- cum := cum + nums [i]
- r := cum mod p
- 如果（r-s）mod p存在于d中，则
  - ans := ans和 i – d [(r-s) mod p]的最小值
- d [r] ：= i
如果ans＜nums的大小，则返回ans否则返回-1

例子

让我们看一下以下实现以获得更好的理解-

def solve(nums, p):
   ans = float("inf")
   s = sum(nums) % p
   d = {0:-1}
   cum = 0
   if s == 0:
      return 0
   for i in range(len(nums)):
      cum+=nums[i]
      r = cum%p
      if (r-s)%p in d:
         ans = min(ans, i-d[(r-s)%p])
      d[r] = i
   return ans if ans<len(nums) else -1

nums = [8,2,6,5,3]
p = 7
print(solve(nums, p))