Chương trình làm cho tổng mảng chia hết cho P trong Python

Cho mảng nums và p. Xóa 1 mảng con (không phải toàn bộ) sao cho tổng phần còn lại chia hết cho p. Tìm độ dài mảng con nhỏ nhất cần xóa, -1 nếu không thể.

Ví dụ: nums=[8,2,6,5,3], p=7 → 1. Xóa [3], tổng còn lại = 21 chia hết 7.

Giải thuật (Prefix sum + Hash map)

1. s = sum(nums) % p. Nếu s == 0: trả về 0.
2. Cần xóa mảng con có tổng ≡ s (mod p).
3. Duyệt tính prefix sum cum, r = cum % p.
4. Map d[r] = index lưu chỉ số cuối cùng có prefix mod = r.
5. Tìm (r - s) % p trong d: độ dài = i - d[(r-s)%p], cập nhật min.
6. Trả về min nếu < n else -1.

Ví dụ minh họa

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

Đầu vào

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

Đầu ra

1