ตรวจสอบว่าแอรเรย์แบ่งเป็นคู่ที่ผลรวมหาร k ลงตัวได้หรือไม่ใน Python

ภาพรวม

บทความนี้แก้ปัญหา: กำหนดแอรเรย์และเลข k ต้องการทราบว่าแบ่งแอรเรย์เป็นคู่ได้หรือไม่ ที่ผลรวมของแต่ละคู่ หาร k ลงตัว

หลักการทางคณิตศาสตร์

สองจำนวน a, b มีผลรวมหาร k ลงตัว ก็ต่อเมื่อ (a%k + b%k) % k == 0 กล่าวคือ เศษของ a และ b ต้อง "เติมกัน" ให้ครบ k (เช่น เศษ 2 กับเศษ 5 เมื่อ k=7)

อัลกอริทึม

1. ถ้าจำนวน元素เป็นคี่ คืนค่า False ทันที
2. นับความถี่ของแต่ละเศษ (remainder = ((num % k) + k) % k เพื่อจัดการเลขติดลบ)
3. ตรวจสอบเงื่อนไข:
   • เศษ 0: ต้องมีจำนวนคู่
   • เศษ k/2 (ถ้า k คู่): ต้องมีจำนวนคู่
   • เศษอื่น: จำนวนของเศษ r ต้องเท่ากับเศษ k-r

ตัวอย่างโค้ด Python

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))  # True (5+9=14, 15+6=21)

ผลลัพธ์

True

คำอธิบายเพิ่มเติม

ตัวอย่าง: 5%7=5, 9%7=2 (5+2=7), 15%7=1, 6%7=6 (1+6=7) โค้ดจัดการเลขติดลบได้ด้วยการ ((num%k)+k)%k