โปรแกรมทำให้ผลรวมหารพีลงตัวใน Python

ปัญหา

อาร์เรย์ nums และ p ลบ subarray (ไม่ใช่ทั้งอาร์เรย์) น้อยที่สุด ให้ผลรวมที่เหลือหาร p ลงตัว หาความยาว subarray นั้น

ตัวอย่าง

nums=[8,2,6,5,3], p=7 → 1 (ลบ 3 เหลือ 21 หาร 7 ลงตัว)

ขั้นตอนการแก้ปัญหา

1. ans := inf, s := sum(nums) % p
2. d := {0: -1}, cum := 0
3. ถ้า s == 0: คืน 0
4. วน i 0..n-1:
   • cum += nums[i]
   • r := cum % p
   • ถ้า (r - s) % p in d: ans = min(ans, i - d[(r-s)%p])
   • d[r] = i
5. คืน ans if ans < len(nums) else -1

การนำไปใช้งาน (Python)

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