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
  • 對於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))

輸入

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

輸出

1

更新於: 2021年10月4日

325 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告