Chương trình kiểm tra có thể chia danh sách thành cặp tổng chia hết cho k bằng Python

Cho danh sách nums và số k. Kiểm tra có thể phân hoạch nums thành các cặp sao cho tổng mỗi cặp chia hết cho k.

Ví dụ: nums=[4,7,2,5], k=6 → True (cặp (4,2) và (7,5), tổng 6 và 12 chia hết 6).

Giải thuật

• Nếu độ dài nums lẻ → False.
• Đếm tần suất dư modulo k vào mảng count.
• Số dư 0 phải có tần suất chẵn.
• Với mỗi i = 1..k//2: count[i] == count[k-i].
• Trả về True nếu thỏa mãn tất cả.

Ví dụ minh họa

class Solution:
    def solve(self, nums, k):
        if len(nums) % 2:
            return False
        count = [0] * k
        for n in nums:
            count[n % k] += 1
        if count[0] % 2:
            return False
        for i in range(1, k // 2 + 1):
            if count[i] != count[k - i]:
                return False
        return True

ob = Solution()
nums = [4, 7, 2, 5]
k = 6
print(ob.solve(nums, k))

Đầu vào

[4, 7, 2, 5], 6

Đầu ra

True