Giả sử chúng ta có một mảng các số và một số k, cần kiểm tra xem mảng có thể chia thành các cặp sao cho tổng của mỗi cặp chia hết cho k hay không.
Ví dụ, nếu đầu vào là arr = [5, 15, 6, 9], k = 7, thì đầu ra sẽ là True vì có thể tạo các cặp (5, 9) và (15, 6).
Các bước giải quyết:
- n := kích thước mảng.
- Nếu n là số lẻ, trả về False.
- occurrences := từ điển mặc định giá trị 0.
- Duyệt i từ 0 đến n-1: tăng occurrences[((array[i] % k) + k) % k] lên 1 (xử lý số âm).
- Duyệt i từ 0 đến n-1:
- remainder := ((array[i] % k) + k) % k.
- Nếu 2 * remainder == k: nếu occurrences[remainder] là lẻ, trả về False.
- Ngược lại nếu remainder == 0: nếu occurrences[remainder] là lẻ, trả về False.
- Ngược lại nếu occurrences[remainder] != occurrences[k - remainder], trả về False.
- Trả về True.
Xem ví dụ dưới đây để hiểu rõ hơn:
Ví dụ
from collections import defaultdict
def solve(array, k):
n = len(array)
if n % 2 != 0:
return False
occurrences = defaultdict(lambda: 0)
for i in range(n):
occurrences[((array[i] % k) + k) % k] += 1
for i in range(n):
remainder = ((array[i] % k) + k) % k
if (2 * remainder == k):
if (occurrences[remainder] % 2 != 0):
return False
elif (remainder == 0):
if (occurrences[remainder] & 1):
return False
elif (occurrences[remainder] != occurrences[k - remainder]):
return False
return True
arr = [5, 15, 6, 9]
k = 7
print(solve(arr, k))
Đầu vào
[5, 15, 6, 9], 7
Đầu ra
True