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

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

औपचारिक रूप से, हम ऐरे को विभाजित कर सकते हैं यदि हम इंडेक्स i+1 < j ढूंढ सकते हैं जैसे कि (A[0] + A[1] + ... + A[i], A[i+1] + A[i+2] + ... + A[j-1] और A[j] + A[j-1] + ... + A[A.length - 1] के समान हो)।

इसलिए यदि इनपुट [0,2,1,-6,6,-7,9,1,2,0,1] है, तो आउटपुट true होगा। तीन ऐरे होंगे [0,2,1], [-6,6,-7,9,1] और [2,0,1]।

समाधान के चरण

• temp := सभी एलिमेंट्स का योग, और required_sum := temp / 3
• sum_left सेट करें बाएं से दाएं क्युमुलेटिव योग स्टोर करने के लिए
• sum_right सेट करें दाएं से बाएं क्युमुलेटिव योग स्टोर करने के लिए
• index1 := 0 और index2 := ऐरे की लंबाई - 1
• जब तक index1 < index2:
  • जब तक index1 < index2 और sum_left[index1] != required_sum
    • index1 := index1 + 1
  • जब तक index2 > index1 और sum_right[index2] != required_sum
    • index2 := index2 - 1
  • यदि index1 < index2 और index1 != index2, तो true लौटाएं, अन्यथा false

उदाहरण

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

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