পাইথন - অ্যারে থেকে এমন একটি উপাদান খুঁজে বের করা যা দুটি সাবঅ্যারেতে সমান গুণফল দেয়

একটি অ্যারে দেওয়া থাকলে, এমন একটি উপাদান খুঁজে বের করতে হবে যা অ্যারেকে দুটি সাবঅ্যারে ভাগ করবে যাতে বামপাশের সব উপাদানের গুণফল = ডানপাশের সব উপাদানের গুণফল। এই সমস্যাটি প্রিফিক্স ও সাফিক্স প্রোডাক্ট (Prefix/Suffix Product) ব্যবহার করে O(N)-এ সমাধান করা যায়।

সমস্যা বিবরণ

ইনপুট: [2, 5, 3, 2, 5]
আউটপুট: 3

ব্যাখ্যা: ইনডেক্স ২-এ 3 আছে। বাম সাবঅ্যারে: [2, 5] → গুণফল = ১০। ডান সাবঅ্যারে: [2, 5] → গুণফল = ১০। সমান! তাই 3 হলো উত্তর।

অ্যালগরিদম: প্রিফিক্স ও সাফিক্স প্রোডাক্ট

def find_partition_element(arr):
    n = len(arr)
    if n < 3:
        return -1  # কমপক্ষে ৩ এলিমেন্ট লাগে (একটি পিভট + বাম/ডানে কমপক্ষে ১টি)
    
    # ১. প্রিফিক্স প্রোডাক্ট অ্যারে তৈরি
    prefix_prod = [0] * n
    prefix_prod[0] = arr[0]
    for i in range(1, n):
        prefix_prod[i] = prefix_prod[i - 1] * arr[i]
    
    # ২. সাফিক্স প্রোডাক্ট অ্যারে তৈরি
    suffix_prod = [0] * n
    suffix_prod[n - 1] = arr[n - 1]
    for i in range(n - 2, -1, -1):
        suffix_prod[i] = suffix_prod[i + 1] * arr[i]
    
    # ৩. প্রতিটি সম্ভাব্য পিভট চেক করুন (ইনডেক্স ১ থেকে n-2)
    for i in range(1, n - 1):
        if prefix_prod[i] == suffix_prod[i]:
            return arr[i]
    
    return -1

# টেস্ট
test_cases = [
    [2, 5, 3, 2, 5],        # 3
    [1, 2, 3, 4, 5],        # -1
    [10, 5, 2, 10],         # 2 (10*5=50, 10=10? না... চেক করুন)
    [2, 2, 2, 2],           # 2 (index 1: left=2, right=2*2=4? না)
    [1, 1, 1],              # 1 (left=1, right=1)
]

for arr in test_cases:
    result = find_partition_element(arr)
    print(f"Array: {arr} -> Partition Element: {result}")

সঠিক লজিক: পিভট উপাদানটি বাদ দেওয়া

মূল আর্টিকেলের কোডে একটি বাগ রয়েছে: প্রিফিক্স এবং সাফিক্স উভয়েই পিভট এলিমেন্টটি অন্তর্ভুক্ত করে। সঠিক লজিক হলে পিভট বাদ দিতে হবে।

def find_partition_element_correct(arr):
    n = len(arr)
    if n < 3:
        return -1
    
    # প্রিফিক্স প্রোডাক্ট: prefix[i] = arr[0] * ... * arr[i]
    prefix = [1] * n
    prefix[0] = arr[0]
    for i in range(1, n):
        prefix[i] = prefix[i-1] * arr[i]
    
    # সাফিক্স প্রোডাক্ট: suffix[i] = arr[i] * ... * arr[n-1]
    suffix = [1] * n
    suffix[n-1] = arr[n-1]
    for i in range(n-2, -1, -1):
        suffix[i] = suffix[i+1] * arr[i]
    
    # পিভট i: বাম = prefix[i-1], ডান = suffix[i+1]
    for i in range(1, n-1):
        if prefix[i-1] == suffix[i+1]:
            return arr[i]
    
    return -1

# টেস্ট
print(find_partition_element_correct([2, 5, 3, 2, 5]))  # 3
print(find_partition_element_correct([1, 2, 3, 4, 5]))  # -1
print(find_partition_element_correct([1, 1, 1]))        # 1

ওভারফ্লো হ্যান্ডলিং (বড় সংখ্যার জন্য)

গুণফল খুব দ্রুত বড় হয়। পাইথনে অটোমেটিক বিগ ইন্টিজার সাপোর্ট আছে, কিন্তু অন্যান্য ল্যাঙ্গুয়েজে বা পারফরম্যান্সের জন্য log ব্যবহার করা হয়:

import math

def find_partition_log(arr):
    """Log-space এ তুলনা করে ওভারফ্লো এড়ানো"""
    n = len(arr)
    if n < 3:
        return -1
    
    # Log prefix sum
    log_prefix = [0.0] * n
    log_prefix[0] = math.log(arr[0])
    for i in range(1, n):
        log_prefix[i] = log_prefix[i-1] + math.log(arr[i])
    
    # Log suffix sum
    log_suffix = [0.0] * n
    log_suffix[n-1] = math.log(arr[n-1])
    for i in range(n-2, -1, -1):
        log_suffix[i] = log_suffix[i+1] + math.log(arr[i])
    
    # তুলনা (ফ্লোটিং পয়েন্ট প্রিসিশন বিবেচনা)
    eps = 1e-10
    for i in range(1, n-1):
        if abs(log_prefix[i-1] - log_suffix[i+1]) < eps:
            return arr[i]
    return -1

কমপ্লেক্সিটি

স্পেস অপ্টিমাইজড ভার্সন (O(1) এক্সট্রা স্পেস)

def find_partition_O1_space(arr):
    n = len(arr)
    if n < 3:
        return -1
    
    # টোটাল প্রোডাক্ট
    total = 1
    for x in arr:
        total *= x
    
    left_prod = 1
    for i in range(n - 1):
        left_prod *= arr[i]
        right_prod = total // (left_prod * arr[i]) if arr[i] != 0 else 0
        
        if left_prod == right_prod:
            return arr[i]
    
    return -1