ตรวจสอบว่าแบ่งอาร์เรย์เป็น 2 ส่วนได้ผลต่างเป็น K หรือไม่ ใน Python

ปัญหา

ให้อาร์เรย์ input_list และค่า n ตรวจสอบว่าสามารถแบ่งเป็น 2 ส่วน (prefix/suffix) ได้ที่ผลต่างของผลรวม = n หรือไม่

ตัวอย่าง

input_list = [9,2,5,6], n = 0
Total = 22
Prefix sum: 9, 11, 16, 22
Suffix sum: 13, 11, 6, 0
Diff: |9-13|=4, |11-11|=0 ✓ → "Possible"

แนวคิดการแก้ปัญหา

1. Total sum = S
2. ต้องการ |prefix - (S - prefix)| = n → |2×prefix - S| = n
3. → 2×prefix = S ± n → prefix = (S ± n)/2
4. ดังนั้น (S - n) ต้องเป็นเลขคู่ และมี prefix sum = (S - n)/2

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

def solve(arr, n):
    total = sum(arr)
    if (total - n) % 2 != 0:
        return "Not Possible"
    target = (total - n) // 2
    prefix_sum = 0
    for val in arr:
        prefix_sum += val
        if prefix_sum == target:
            return "Possible"
    return "Not Possible"

print(solve([9, 2, 5, 6], 0))  # Possible

อินพุต / เอาต์พุต

Input:  [9,2,5,6], 0
Output: Possible