Pythonで合計をPで割り切れるプログラム

配列numsと別の値pがあるとすると、残りの値の合計がpで割り切れるように、最小のサブ配列（配列全体ではない）を削除します。削除する必要のある最小のサブ配列の長さを見つける必要があります。そのようなサブ配列がない場合は、-1を返します。

したがって、入力がnums =[8,2,6,5,3] p =7のような場合、出力は1になります。これは、3を削除すると、合計が21になり、7で割り切れるからです。

これを解決するには、次の手順に従います-

• ans：=無限大
• s：=（numsのすべての要素の合計）mod p
• d：=マップにキーと値のペアが含まれている{0：-1}
• cum：=0
• sが0と同じ場合、
  • 0を返す
• 0からnumsのサイズの範囲のiの場合は、
  • 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 を返します。

例

理解を深めるために、次の実装を見てみましょう-

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))

入力

[8,2,6,5,3], 7

出力

1