Chương trình Python tìm độ dài dãy con nhỏ nhất xóa để tổng chia hết cho k

Cho mảng nums (số dương) và k > 0. Tìm độ dài dãy con liên tiếp ngắn nhất (có thể rỗng) để xóa, sao cho tổng phần tử còn lại chia hết cho k. Không được xóa toàn bộ mảng. Trả về -1 nếu không tồn tại.

Ví dụ

Input: nums = [5,8,6,3], k = 8

Output: 1

Giải thích: Tổng = 22. Xóa [6] (độ dài 1) → tổng còn 16 chia hết 8.

Thuật toán (Prefix Sum + Hash Map)

1. Tính rem = sum(nums) % k. Nếu rem == 0 → trả về 0 (không cần xóa).
2. Cần tìm dãy con có tổng % k = rem (vì (total - sub) % k == 0 ⟺ sub % k == rem).
3. Duyệt mảng, tính prefix sum modulo k. Dùng dictionary mp lưu mod_value → chỉ số cuối cùng.
4. Tại chỉ số i với prefix mod m, cần tìm prefix mod (m - rem + k) % k đã xuất hiện trước đó.
5. Cập nhật độ dài nhỏ nhất.

Mã nguồn Python

def solve(nums, k):
    rem = sum(nums) % k
    if rem == 0:
        return 0

    n = len(nums)
    mp = {0: -1}
    presum = 0
    res = n

    for i in range(n):
        presum += nums[i]
        m = presum % k
        mp[m] = i
        need = (m - rem + k) % k
        if need in mp:
            res = min(res, i - mp[need])

    return res if res != n else -1

# Test
nums = [5, 8, 6, 3]
k = 8
print(solve(nums, k))  # Output: 1

Độ phức tạp

• Thời gian: O(n)
• Không gian: O(min(n, k)) cho hash map.