โปรแกรมหาตัวซ้ำในลิสต์ขนาด n+1 จากช่วง 1..n ใน Python

ให้ลิสต์ nums ขนาด n+1 ค่าอยู่ใน 1..n ต้องมีตัวซ้ำ (Pigeonhole) หาตัวซ้ำ O(n) Time, O(1) Space

ตัวอย่าง: nums=[2,1,4,3,5,4] → 4

ขั้นตอน (Math Sum)

1. q = sum(nums)
2. n = len(nums)
3. v = (n-1)*n//2 (ผลรวม 1..n-1)
4. คืน q - v

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

def solve(nums):
    q = sum(nums)
    n = len(nums)
    v = (n - 1) * n // 2
    return q - v

nums = [2,1,4,3,5,4]
print(solve(nums))  # Output: 4

อินพุต

[2,1,4,3,5,4]

เอาต์พุต

4