โปรแกรมตรวจสอบว่า array สามารถจับคู่ได้ทุกคู่หาร k ลงตัวหรือไม่ด้วย Python

สมมติว่าเรามีอาร์เรย์ nums ที่มีจำนวนอิลิเมนต์เป็นเลขคู่ และมีค่า k เราต้องแบ่ง nums เป็น n/2 คู่ ที่ผลรวมของแต่ละคูาหาร k ลงตัว ถ้าทำได้คืน True มิฉะนั้นคืน False

เช่น ถ้าข้อมูลเข้าเป็น nums = [9,5,3,4,7,10,20,8] k = 3 ผลลัพธ์จะเป็น True เพราะจับคู่ได้เป็น (9,3), (5,7), (4,20), (8,10) ผลรวมทุกคูาหาร 3 ลงตัว

ขั้นตอนการแก้ปัญหา

• สร้างลิสต์ dp และตัวนับ count = 0
• วนลูปแต่ละ x ใน nums:
  • t = k - (x % k)
  • ถ้า t == k (คือ x % k == 0): count += 1
  • มิฉะนั้น: เพิ่ม t เข้า dp
• ถ้า count เป็นเลขคี่: คืน False (คู่ที่ mod 0 ต้องจับคู่กันเอง ต้องเป็นเลขคู่)
• เรียงลำดับ dp
• ใช้ two pointers: low = 0, high = len(dp) - 1
  • วนลูป while low < high:
    • ถ้า dp[low] + dp[high] != k: คืน False
    • low += 1, high -= 1
• คืน True

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

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))

ข้อมูลเข้า

[9,5,3,4,7,10,20,8], 3

ข้อมูลออก

True