पायथन में समान योग के साथ तीन भागों में विभाजन सरणी

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी A है, तो हमारा आउटपुट सही होगा यदि और केवल तभी हम सरणी को तीन गैर-रिक्त भागों में विभाजित कर सकते हैं, जिनका योग बराबर है।

औपचारिक रूप से, हम सरणी को विभाजित कर सकते हैं यदि हम इंडेक्स i+1

तो अगर इनपुट [0,2,1,-6,6,-7,9,1,2,0,1] है, तो आउटपुट सही होगा। तीन सरणियाँ [0,2,1], [-6,6,-7,9,1] और [2,0,1]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• अस्थायी:=सभी तत्वों का योग, और आवश्यक_योग:=अस्थायी / 3
• समुच्चय योग को बाएँ से दाएँ संग्रहीत करने के लिए sum_left सेट करें
• समुच्चय योग को दाएं से बाएं स्टोर करने के लिए sum_right सेट करें
• सूचकांक1:=0 और अनुक्रमणिका2:=सरणी की लंबाई - 1
• जबकि अनुक्रमणिका1 <अनुक्रमणिका2:
  • जबकि अनुक्रमणिका1 <अनुक्रमणिका2 और sum_left[index1] !=आवश्यक_योग
    • सूचकांक1 :=अनुक्रमणिका1 + 1
  • जबकि अनुक्रमणिका2> अनुक्रमणिका1 और sum_right[index2] !=आवश्यक_योग
    • सूचकांक2 :=अनुक्रमणिका2 - 1
  • यदि अनुक्रमणिका1 <अनुक्रमणिका2 और अनुक्रमणिका1 !=अनुक्रमणिका2, तो सत्य लौटाएं, अन्यथा असत्य

उदाहरण

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

class Solution(object):
   def canThreePartsEqualSum(self, A):
      temp = sum(A)
      if (temp%3 != 0):
         return 0
      sum_left=[0 for i in range(len(A))]
      sum_left[0] = A[0]
      sum_right=[0 for i in range(len(A))]
      sum_right[-1] = A[-1]
      for i in range(1,len(A)):
         sum_left[i] = A[i]+sum_left[i-1]
      for i in range(len(A)-2,-1,-1):
         sum_right[i] = A[i]+sum_right[i+1]
      #print(sum_left,sum_right)
      required_sum = temp/3
      index1 = 0
      index2 = len(A)-1
      while index1 < index2:
      while index1 <index2 and sum_left[index1]!=required_sum:
         index1+=1
      while index2>index1 and sum_right[index2]!=required_sum:
         index2-=1
      return index1<index2 and index1 != index2
ob1 = Solution()
print(ob1.canThreePartsEqualSum([0,2,2,-6,6,-7,9,2,2,0,2]))

इनपुट

[0,2,1,-6,6,-7,9,1,2,0,1]

आउटपुट

true