পাইথনে যে সমষ্টিগুলির জন্য একটি অ্যারেকে সমান সমষ্টির সাব্যারেতে ভাগ করা যায় তা সন্ধান করুন

ধরুন আমাদের পূর্ণসংখ্যা A এর একটি অ্যারে আছে; আমাদের যোগফলের জন্য সমস্ত মান খুঁজে বের করতে হবে যাতে একটি মানের যোগফলের জন্য অ্যারেটিকে যোগফলের উপ-অ্যারেতে ভাগ করা যায় [i]। যদি আমরা অ্যারেটিকে সমান যোগফলের সাব-অ্যারেতে ভাগ করতে না পারি তাহলে -1 রিটার্ন করুন।

সুতরাং, যদি ইনপুটটি A =[2, 4, 2, 2, 2, 4, 2, 6] এর মতো হয় তবে আউটপুট হবে [6,8,12] কারণ অ্যারেটিকে সাব-অ্যারেতে ভাগ করা যেতে পারে। যোগফল 6, 8 এবং 12। এগুলি নিম্নরূপ:[{2, 4}, {2, 2, 2}, {4, 2}, {6}] [{2, 4, 2}, {2, 2 , 4},{2, 6}] [{2, 4, 2, 2, 2},{4, 2, 6

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=a

  এর আকার

• টেবিল :=n আকারের একটি অ্যারে এবং 0

  দিয়ে ভরা

• টেবিল[0] :=a[0]

• 1 থেকে n রেঞ্জের জন্য, করুন

  • টেবিল[i] :=a[i] + টেবিল[i - 1]

• S :=টেবিল[n - 1]

• my_map :=একটি নতুন মানচিত্র

• 0 থেকে n রেঞ্জের জন্য, করুন

  • my_map[টেবিল[i]] :=1

• উত্তর :=একটি নতুন সেট

• i এর জন্য রেঞ্জ 1 থেকে পূর্ণসংখ্যা অংশ (S) এর বর্গমূল + 1, do

  • যদি S mod i 0 এর মত হয়, তাহলে

    • is_present :=সত্য

    • part_1 :=i

    • part_2 :=S / i

      এর ভাগফল

    • j এর জন্য পরিসর part_1 থেকে S + 1, part_1 দ্বারা প্রতিটি ধাপে আপডেট করুন, করুন

      • যদি j my_map-এ না থাকে, তাহলে

        • is_present :=মিথ্যা

        • লুপ থেকে বেরিয়ে আসুন

    • যদি is_present সত্য হয় এবং part_1 S এর মত না হয়, তাহলে

      • উত্তর যোগ করুন(part_1)

    • is_present :=সত্য

    • (S / i) থেকে S + 1 পর্যন্ত j এর পরিসীমা ভাগফলের জন্য, প্রতিটি ধাপে S // i দ্বারা আপডেট করুন, করুন

      • যদি j my_map-এ না থাকে, তাহলে

        • is_present :=মিথ্যা;

        • লুপ থেকে বেরিয়ে আসুন

    • যদি is_present এবং part_2 S এর মত না হয়, তাহলে

      • উত্তর যোগ করুন(part_2)

• যদি উত্তরের আকার 0 এর মতো হয়, তাহলে

  • রিটার্ন -1

• প্রত্যাবর্তন উত্তর

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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))

ইনপুট

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

আউটপুট

{8, 12, 6}