หาจำนวนเต็มบวกน้อยที่สุดที่ไม่สามารถเป็นผลรวม Subset ของอาร์เรย์ที่เรียงแล้วได้ใน Python

Smallest Positive Integer Not Representable as Subset Sum

กำหนดอาร์เรย์ A ที่เรียงจากน้อยไปมากและมีค่าบวกทั้งหมด หาจำนวนเต็มบวกน้อยที่สุดที่ ไม่สามารถ สร้างได้จากผลรวมของ Subset ใดๆ ของ A ทำได้ใน O(N)

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

แนวคิด

เก็บค่า answer = ค่าที่ยังสร้างไม่ได้น้อยที่สุด (เริ่มต้น = 1) วนอ่านอาร์เรย์:

• ถ้า A[i] <= answer → สร้างค่าทุกค่าจนถึง answer + A[i] - 1 ได้ → อัปเดต answer += A[i]
• ถ้า A[i] > answer → มีช่องว่าง → answer คือคำตอบ หยุดลูป

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

def get_smallest_element(A):
    answer = 1
    for x in A:
        if x <= answer:
            answer += x
        else:
            break
    return answer

print(get_smallest_element([1, 4, 8, 12, 13, 17]))  # 2