পাইথনে অ্যারেকে সমান যোগফলवाले সাবঅ্যারে-এ ভাগ করার যোগফল মানগুলো বের করুন

সমস্যা বিবরণ

একটি ইন্টিজার অ্যারে A দেওয়া আছে। সেই সব যোগফল মান বের করতে হবে যাতে অ্যারেটিকে সাবঅ্যারে-এ ভাগ করা যায় যেখানে প্রতিটি সাবঅ্যারে-এর যোগফল সেই মানের সমান। না পারলে -1 রিটার্ন করুন।

উদাহরণস্বরূপ, A=[2,4,2,2,2,4,2,6] হলে আউটপুট [6,8,12] কারণ অ্যারেটিকে যোগফল ৬, ৮, ১২-वाले সাবঅ্যারে-এ ভাগ করা যায়।

সমাধানের ধাপসমূহ

1. প্রিফিক্স সম অ্যারে table বানান।
2. মোট যোগফল S = table[n-1]।
3. প্রিফিক্স সমগুলো একটি ম্যাপ my_map-এ স্টোর করুন।
4. 1 থেকে sqrt(S) পর্যন্ত লুপ চালান:
   • যদি S % i == 0 হয়, তবে i এবং S//i দুটি ক্যান্ডিডেট।
   • প্রতিটি ক্যান্ডিডেট part এর জন্য: part, 2*part, 3*part, ... S সব প্রিফিক্স সমে আছে কিনা চেক করুন।
   • যদি সব থাকে, তবে part একটি বৈধ যোগফল।
5. সব বৈধ যোগফল সেটে সংগ্রহ করুন এবং রিটার্ন করুন।

পাইথন কোড উদাহরণ

from math import sqrt

def find_sum(a):
    n = len(a)
    table = [0] * n
    table[0] = a[0]
    for i in range(1, n):
        table[i] = a[i] + table[i-1]
    S = table[n-1]
    my_map = {}
    for i in range(n):
        my_map[table[i]] = 1
    answer = set()
    for i in range(1, int(sqrt(S)) + 1):
        if S % i == 0:
            is_present = True
            part_1 = i
            part_2 = S // i
            for j in range(part_1, S + 1, part_1):
                if j not in my_map:
                    is_present = False
                    break
            if is_present and part_1 != S:
                answer.add(part_1)
            is_present = True
            for j in range(S // i, S + 1, S // i):
                if j not in my_map:
                    is_present = False
                    break
            if is_present and part_2 != S:
                answer.add(part_2)
    if len(answer) == 0:
        return -1
    return answer

a = [2, 4, 2, 2, 2, 4, 2, 6]
print(find_sum(a))  # আউটপুট: {8, 12, 6}

ইনপুট

[2, 4, 2, 2, 2, 4, 2, 6]

আউটপুট

{8, 12, 6}