उन योगों का पता लगाएं जिनके लिए एक सरणी को समान योग के उप-सरणी में पायथन में विभाजित किया जा सकता है

मान लीजिए कि हमारे पास पूर्णांक ए की एक सरणी है; हमें योग के लिए सभी मानों को खोजना होगा ताकि एक मान के लिए योग [i] सरणी को योग योग [i] के उप-सरणी में विभाजित किया जा सके। यदि हम सरणी को समान योग के उप-सरणी में विभाजित नहीं कर सकते हैं तो -1 लौटाएं।

इसलिए, यदि इनपुट ए =[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 :=आकार का

• तालिका:=आकार n की एक सरणी और 0 से भरी हुई

• तालिका [0] :=a[0]

• 1 से n की सीमा में i के लिए, करें

  • टेबल [i] :=a[i] + टेबल[i - 1]

• एस:=टेबल [एन -1]

• my_map :=एक नया नक्शा

• मेरे लिए 0 से n की सीमा में, करें

  • my_map[तालिका[i]] :=1

• उत्तर:=एक नया सेट

• i के लिए श्रेणी 1 से पूर्णांक भाग ((S) का वर्गमूल) + 1, करें

  • यदि S mod i 0 के समान है, तो

    • is_वर्तमान :=सत्य

    • part_1 :=मैं

    • part_2 :=S / i का भागफल

    • j के लिए part_1 से S + 1 की श्रेणी में, प्रत्येक चरण में part_1 द्वारा अपडेट करें, करें

      • अगर j my_map में नहीं है, तो

        • is_वर्तमान :=असत्य

        • लूप से बाहर आएं

    • यदि is_present सत्य है और part_1 S के समान नहीं है, तो

      • उत्तर का (भाग_1) जोड़ें

    • is_वर्तमान :=सत्य

    • j के लिए (S / i) से S + 1 के श्रेणी भागफल में, प्रत्येक चरण में S // i, do द्वारा अपडेट करें

      • अगर j my_map में नहीं है, तो

        • is_वर्तमान :=असत्य;

        • लूप से बाहर आएं

    • यदि is_present और part_2 S के समान नहीं है, तो

      • उत्तर का (भाग_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}