সমস্যা বিবরণ
ইন্টিজার অ্যারে A দেওয়া আছে। অ্যারেটিকে তিনটি নন-এমপ্টি পার্টে ভাগ করা যায় কিনা যাতে তিনটির সমান থাকে - তা বের করতে হবে (true/false)।
ফরম্যালি: i+1 < j এমন ইনডেক্স পাওয়া যায় কিনা যেন sum(A[0..i]) == sum(A[i+1..j-1]) == sum(A[j..n-1])।
উদাহরণ: [0,2,1,-6,6,-7,9,1,2,0,1] → true (পার্ট: [0,2,1], [-6,6,-7,9,1], [2,0,1] - প্রতিটির সম ৩)।
সমাধানের পদ্ধতি
- মোট সম = sum(A)। যদি ৩ দিয়ে বিভাজ্য না হয়, false ফেরত দিন।
- প্রতিটি পার্টের সম = total / 3।
- বাম থেকে ক্যুমুলেটিভ সম (sum_left) এবং ডান থেকে ক্যুমুলেটিভ সম (sum_right) বের করুন।
- দুটি পয়েন্টার index1 (বাম) এবং index2 (দান) দিয়ে target সম পাওয়া পর্যন্ত এগিয়ে যান।
- যদি index1 < index2 এবং index1 != index2 হয়, true ফেরত দিন।
পাইথন উদাহরণ
class Solution(object):
def canThreePartsEqualSum(self, A):
total = sum(A)
if total % 3 != 0:
return False
target = total // 3
sum_left = [0] * len(A)
sum_left[0] = A[0]
for i in range(1, len(A)):
sum_left[i] = sum_left[i-1] + A[i]
sum_right = [0] * len(A)
sum_right[-1] = A[-1]
for i in range(len(A)-2, -1, -1):
sum_right[i] = sum_right[i+1] + A[i]
index1 = 0
index2 = len(A) - 1
while index1 < index2:
while index1 < index2 and sum_left[index1] != target:
index1 += 1
while index2 > index1 and sum_right[index2] != target:
index2 -= 1
if index1 < index2 and index1 != index2:
return True
return False
ob1 = Solution()
print(ob1.canThreePartsEqualSum([0,2,1,-6,6,-7,9,1,2,0,1]))
ইনপুট
[0,2,1,-6,6,-7,9,1,2,0,1]
আউটপুট
True
স্পেস-অপ্টিমাইজড (O(1) স্পেস)
def canThreePartsEqualSum(A):
total = sum(A)
if total % 3 != 0:
return False
target = total // 3
left_sum = 0
count = 0
for i in range(len(A) - 1): # শেষ পার্ট নন-এমপ্টি থাকতে হবে
left_sum += A[i]
if left_sum == target:
count += 1
left_sum = 0
if count == 2:
return True
return False
