Pythonで合計をkで割り切れるようにするために削除できる最小のサブリストの長さを見つけるプログラム

numsと呼ばれる正の値のリストがあり、正の数kもあるとします。残りの要素の合計がkで割り切れるように、numsから削除できる最短のサブリスト（空の場合もあります）の長さを見つける必要があります。ただし、リスト全体を削除することはできません。削除するサブリストがない場合は、-1を返します。

したがって、入力がnums =[5,8,6,3] k =8のような場合、[5,8,6,3]の要素の現在の合計は22であるため、出力は1になります。長さ1のサブリスト[6]を削除すると、合計は16になり、8で割り切れます。

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

• rem：=（nums + kに存在するすべての要素の合計）mod k
• remが0と同じ場合、
  • 0を返す
• n：=numsのサイズ
• 推定：=0
• mp：=辞書、最初はキー0に-1を格納します
• res：=n
• 0からn-1の範囲のiの場合、do
  • presum：=presum + nums [i]
  • m：=（presum + k）mod k
  • mp [m]：=i
  • （m --rem + k）mod kがmpに存在する場合、
    • res：=最小のresおよび（i --mp [（m --rem + k）mod k]）
• resがnと同じでない場合はresを返し、それ以外の場合は-1

例

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

def solve(nums, k):
   rem = (sum(nums) + k) % k
   if rem == 0:
      return 0
   n, presum = len(nums), 0
   mp = {0: -1}
   res = n
   for i in range(n):
      presum += nums[i]
      m = (presum + k) % k
      mp[m] = i
      if (m - rem + k) % k in mp:
         res = min(res, i - mp[(m - rem + k) % k])
   return res if res != n else -1

nums = [5,8,6,3]
k = 8
print(solve(nums, k))

入力

[5,8,6,3], 8

出力

1