Cho mảng nums có số phần tử chẵn và số nguyên k. Kiểm tra xem có thể chia nums thành đúng n/2 cặp sao cho tổng mỗi cặp chia hết cho k hay không.
Ví dụ: nums = [9,5,3,4,7,10,20,8], k = 3. Kết quả True vì có thể tạo cặp (9,3), (5,7), (4,20), (8,10) - tổng các cặp đều chia hết cho 3.
Thuật toán giải quyết
- Tính phần dư cần thiết để bù: t = k - (x % k). Nếu t == k thì t = 0 (tức x đã chia hết k).
- Đếm số phần tử có phần dư 0 (count). Nếu count lẻ → False.
- Các phần tử còn lại lưu phần dư t vào danh sách dp.
- Sắp xếp dp. Dùng hai con trỏ low=0, high=len(dp)-1.
- Nếu dp[low] + dp[high] != k → False.
- low++, high--.
- Nếu duyệt hết → True.
Ví dụ triển khai
def solve(nums, k):
dp = []
count = 0
for x in nums:
t = k - (x % k)
if t == k:
count += 1
else:
dp.append(t)
if count % 2 != 0:
return False
dp.sort()
low = 0
high = len(dp) - 1
while low < high:
if dp[low] + dp[high] != k:
return False
low += 1
high -= 1
return True
nums = [9,5,3,4,7,10,20,8]
k = 3
print(solve(nums, k))Đầu vào
[9,5,3,4,7,10,20,8], 3
Đầu ra
True