หาค่าผลรวมที่ทำให้อาร์เรย์แบ่งเป็น Subarray ผลรวมเท่ากันได้ใน Python

หา Sum ทั้งหมดที่ทำให้อาร์เรย์แบ่งเป็น Subarray ผลรวมเท่ากันได้

กำหนดอาร์เรย์ A ต้องการหาค่า sum ทั้งหมดที่ทำให้สามารถแบ่ง A เป็น Subarray ต่อเนื่องหลายๆ ตัวที่ทุกตัวมีผลรวมเท่ากับ sum นั้นได้

ตัวอย่าง: A = [2,4,2,2,2,4,2,6] → ผลลัพธ์ [6, 8, 12]

แนวคิด

1. คำนวณ Prefix Sum ทั้งอาร์เรย์
2. ผลรวมทั้งหมด S ต้องหารด้วย sum ลงตัว
3. สำหรับแต่ละตัวหาร d ของ S ตรวจสอบว่ามี Prefix Sum ครบทุกคูณของ d (คือ d, 2d, 3d, ..., S) หรือไม่
4. ถ้ามีครบ → d เป็นคำตอบที่ถูกต้อง

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

from math import sqrt

def find_sum(a):
    n = len(a)
    prefix = [0] * n
    prefix[0] = a[0]
    for i in range(1, n):
        prefix[i] = prefix[i-1] + a[i]
    S = prefix[-1]
    prefix_set = set(prefix)
    ans = set()
    for d in range(1, int(sqrt(S)) + 1):
        if S % d == 0:
            # check divisor d
            ok = all(k in prefix_set for k in range(d, S+1, d))
            if ok and d != S:
                ans.add(d)
            # check paired divisor S//d
            d2 = S // d
            ok = all(k in prefix_set for k in range(d2, S+1, d2))
            if ok and d2 != S:
                ans.add(d2)
    return sorted(ans) if ans else -1

print(find_sum([2,4,2,2,2,4,2,6]))  # [6, 8, 12]