ได้อาร์เรย์ขนาด N ต้องการหาองค์ประกอบที่แบ่งอาร์เรย์เป็น 2 sub-arrays ที่มีผลคูณเท่ากัน คืน -1 ถ้าไม่มี
ตัวอย่าง
Input: [2, 5, 3, 2, 5]
Output: 3 (subarrays: {2, 5} และ {2, 5} ผลคูณ = 10)
อัลกอริธึม: Prefix & Suffix Products
def search_element(arr):
n = len(arr)
# Prefix products: multiply_pref[i] = product of arr[0..i]
multiply_pref = []
multiply_pref.append(arr[0])
for i in range(1, n):
multiply_pref.append(multiply_pref[i-1] * arr[i])
# Suffix products: multiply_suff[i] = product of arr[i..n-1]
multiply_suff = [None] * n
multiply_suff[n-1] = arr[n-1]
for i in range(n-2, -1, -1):
multiply_suff[i] = multiply_suff[i+1] * arr[i]
# หาจุดแบ่ง: prefix[i] == suffix[i]
for i in range(1, n-1):
if multiply_pref[i] == multiply_suff[i]:
return arr[i]
return -1
# ทดสอบ
array = [2, 5, 3, 2, 5]
print(search_element(array)) # 3
การทำงานแบบ Step-by-Step
Array: [2, 5, 3, 2, 5]
Prefix products:
i=0: 2
i=1: 2*5 = 10
i=2: 10*3 = 30
i=3: 30*2 = 60
i=4: 60*5 = 300
Suffix products:
i=4: 5
i=3: 2*5 = 10
i=2: 3*10 = 30
i=1: 5*30 = 150
i=0: 2*150 = 300
Compare prefix[i] vs suffix[i]:
i=1: 10 vs 150 ✗
i=2: 30 vs 30 ✓ → return arr[2] = 3
i=3: 60 vs 10 ✗
ปัญหา Overflow และการแก้ไข
ผลคูณอาจใหญ่เกิน (overflow) ในภาษาอื่น แต่ Python รองรับ big integers อัตโนมัติ
สำหรับภาษาอื่น ใช้ Logarithm:
import math
def search_element_log(arr):
"""ใช้ log เพื่อป้องกัน overflow"""
n = len(arr)
# Prefix log sums
pref_log = [0] * n
pref_log[0] = math.log(arr[0])
for i in range(1, n):
pref_log[i] = pref_log[i-1] + math.log(arr[i])
# Suffix log sums
suff_log = [0] * n
suff_log[n-1] = math.log(arr[n-1])
for i in range(n-2, -1, -1):
suff_log[i] = suff_log[i+1] + math.log(arr[i])
# Compare with tolerance
for i in range(1, n-1):
if abs(pref_log[i] - suff_log[i]) < 1e-9:
return arr[i]
return -1
Complexity
- Time: O(n) - single pass สำหรับ prefix, suffix, และ compare
- Space: O(n) - สำหรับ prefix และ suffix arrays
- สามารถลดเป็น O(1) space ได้ด้วย two-pass technique
Space Optimized Version (O(1) space)
def search_element_optimized(arr):
n = len(arr)
total_product = 1
for x in arr:
total_product *= x
left_product = 1
for i in range(n):
# right_product = total_product / left_product / arr[i]
# แต่ต้องระวัง division และ zero
right_product = total_product // (left_product * arr[i]) if arr[i] != 0 else 0
if left_product == right_product:
return arr[i]
left_product *= arr[i]
return -1
สรุป
- ใช้ Prefix/Suffix products หาจุดแบ่ง
- Python ไม่มีปัญหา overflow
- Time O(n), Space O(n) (หรือ O(1) optimized)
- ต้องการ strictly 2 subarrays (แต่ละอันอย่างน้อย 1 element)
