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

मान लीजिए हमारे पास पूर्णांकों का एक ऐरे A है। हमें sum के सभी मान ढूंढने हैं ताकि किसी मान sum[i] के लिए ऐरे को उप-सरणियों में विभाजित किया जा सके जिनमें से प्रत्येक का योग sum[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 := len(a)
• table := [0] * n
• table[0] := a[0]
• i को 1 से n-1 तक: table[i] := a[i] + table[i-1]
• S := table[n-1] (कुल योग)
• my_map := {}
• i को 0 से n-1 तक: my_map[table[i]] := 1
• answer := set()
• i को 1 से int(sqrt(S)) + 1 तक के लिए:
  • यदि S % i == 0:
    • is_present := True
    • part_1 := i
    • part_2 := S // i
    • j को part_1 से S तक part_1 चरण में:
      • यदि j not in my_map, तो is_present := False, ब्रेक करें।
    • यदि is_present और part_1 != S, तो answer.add(part_1)
    • is_present := True
    • j को S // i से S तक S // i चरण में:
      • यदि j not in my_map, तो is_present := False, ब्रेक करें।
    • यदि is_present और part_2 != S, तो answer.add(part_2)
• यदि len(answer) == 0, तो -1 लौटाएं।
• answer लौटाएं।

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

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}