ได้อาร์เรย์ A ต้องการหา indices ทั้งหมดที่ถ้าลบ element ตัวนั้นออก อาร์เรย์ที่เหลือจะเป็น "Good Array" โดย Good Array = มี element หนึ่งตัวที่เท่ากับผลรวมของอีกทั้งหมด ใช้ 1-based indexing
ตัวอย่าง
Input: [10, 4, 6, 2]
Output: [1, 4]
อธิบาย:
- ลบ A[1]=10 → [4, 6, 2] → 6 = 4+2 ✓
- ลบ A[4]=2 → [10, 4, 6] → 10 = 4+6 ✓
อัลกอริธึม: Prefix Sum + Hash Map
from collections import defaultdict
def find_good_indices(A):
n = len(A)
total_sum = sum(A)
freq = defaultdict(int)
for x in A:
freq[x] += 1
good_indices = []
for i in range(n):
# ผลรวมหลังลบ A[i]
remaining_sum = total_sum - A[i]
# ต้องหาร 2 ลงตัว (เพราะ x = sum - x → 2x = sum)
if remaining_sum % 2 == 0:
target = remaining_sum // 2
# ตรวจสอบว่า target มีในอาร์เรย์ที่เหลือ
if target in freq:
# ถ้า target == A[i] ต้องมีอย่างน้อย 2 ตัว
# ถ้า target != A[i] ต้องมีอย่างน้อย 1 ตัว
if (A[i] == target and freq[target] > 1) or (A[i] != target):
good_indices.append(i + 1) # 1-based
return good_indices
# ทดสอบ
A = [10, 4, 6, 2]
print(find_good_indices(A)) # [1, 4]
การทำงานแบบ Step-by-Step
A = [10, 4, 6, 2]
total_sum = 22
freq = {10:1, 4:1, 6:1, 2:1}
i=0, A[i]=10: remaining=12, target=6, freq[6]=1, 10!=6 → good (index 1)
i=1, A[i]=4: remaining=18, target=9, freq[9]=0 → not good
i=2, A[i]=6: remaining=16, target=8, freq[8]=0 → not good
i=3, A[i]=2: remaining=20, target=10, freq[10]=1, 2!=10 → good (index 4)
Result: [1, 4]
Edge Cases
# ทดสอบ edge cases
test_cases = [
[1, 1], # [1, 2] - ลบตัวไหนก็ได้ เหลือ [1] → 1 = 0? ไม่ (empty sum=0)
[2, 2, 2], # [1, 2, 3] - ลบตัวไหน เหลือ [2,2] → 2 = 2 ✓
[0, 0, 0], # [1, 2, 3] - 0 = 0 ✓
[1], # [] - ไม่มี index ที่ valid (n<2)
[5, 5, 10], # [3] - ลบ 10 เหลือ [5,5] → 5=5 ✓
]
for arr in test_cases:
print(f"{arr} -> {find_good_indices(arr)}")
ผลลัพธ์ Edge Cases
[1, 1] -> [] # remaining sum = 1, target = 0.5 (not int)
[2, 2, 2] -> [1, 2, 3] # remaining = 4, target = 2, freq[2]=3 > 1
[0, 0, 0] -> [1, 2, 3] # remaining = 0, target = 0, freq[0]=3 > 1
[1] -> [] # n < 2
[5, 5, 10] -> [3] # remove 10 → [5,5] good
Complexity
- Time: O(n) - single pass สำหรับ sum, freq, และ check
- Space: O(n) - frequency map
Mathematical Insight
หลังลบ A[i] อาร์เรย์ที่เหลือมีผลรวม S' = S - A[i]
ต้องการให้มี x ในอาร์เรย์ที่เหลือ ทำให้ x = S' - x → 2x = S' → x = S'/2
ดังนั้น S' ต้องเป็นเลขคู่ และ S'/2 ต้องมีอยู่ในอาร์เรย์ที่เหลือ
สรุป
- คำนวณ total_sum และ frequency map ครั้งเดียว
- แต่ละ index: remaining_sum = total - A[i]
- ถ้า remaining_sum even และ target = remaining_sum/2 อยู่ใน freq
- ตรวจสอบ frequency condition (target == A[i] ต้องมี > 1)
- Time O(n), Space O(n)
