คำอธิบายปัญหา
กำหนดลิสต์ nums ฟังก์ชัน f(i) ลบ element ตำแหน่ง i แล้วตรวจสอบว่าผลรวมดัชนีคู่ = ผลรวมดัชนีคี่ หรือไม่ หาจำนวน i ที่ทำให้ f(i) = True
ตัวอย่าง
nums = [6, 8, 5, 2, 3] → Output: 2
- ลบ 8 (index 1): [6,5,2,3] → even: 6+2=8, odd: 5+3=8 ✓
- ลบ 2 (index 3): [6,8,5,3] → even: 6+5=11, odd: 8+3=11 ✓
ขั้นตอนการแก้ปัญหา (Prefix Sum)
- สร้าง prefix sum แยกคู่/คี่:
a[0][i]= ผลรวมดัชนีคู่ถึง i-1,a[1][i]= ผลรวมดัชนีคี่ถึง i-1 - ผลรวมทั้งหมด
s = sum(nums) - ลบ index i: even_sum ใหม่ =
a[0][i] + (a[1][n] - a[1][i+1])(ดัชนีหลัง i เปลี่ยน parity) - เงื่อนไข:
2 * even_sum == s - nums[i]
การตนการทำงาน (Python)
def solve(nums):
n = len(nums)
a = [[0] * (n + 1), [0] * (n + 1)]
for i, x in enumerate(nums):
a[0][i + 1] = a[0][i]
a[1][i + 1] = a[1][i]
a[i % 2][i + 1] += x
c = 0
s = sum(nums)
for i in range(n):
e = a[0][i] - a[0][0] + a[1][n] - a[1][i + 1]
if e * 2 == s - nums[i]:
c += 1
return c
nums = [6, 8, 5, 2, 3]
print(solve(nums)) # Output: 2
อินพุต / เอาต์พุต
Input: [6, 8, 5, 2, 3] Output: 2
