পাইথনে অ্যারেকে Kটি সাব-অ্যারেতে সমান সম্ফল দিয়ে পার্টিশন করা সম্ভব কিনা তা যাচাই করা

মান লিজিয়ে আমাদের একটি সংখ্যা অ্যারে আছে যার নাম nums, এবং আরেকটি মান K। আমাদের যাচাই করতে হবে nums-কে Kটি কন্টিগুয়াস (contiguous) সাব-অ্যারেতে পার্টিশন করা যায় কিনা যাতে প্রতিটি সাব-অ্যারের এলিমেন্টগুলোর সমান যোগফল থাকে।

যেমন, ইনপুট যদি nums = [2, 5, 3, 4, 7], k = 3 হয়, তবে আউটপুট হবে True কারণ আমরা তিনটি পার্টিশন বানাতে পারি: [(2, 5), (3, 4), (7)] যেগুলোর প্রতিটির যোগফল ৭।

সমাধানের ধাপসমূহ

• n := nums-এর সাইজ
• cumul_sum := nums-এর সব এলিমেন্টের ক্যুমুলেটিভ সম (cumulative sum)
• total_sum := cumul_sum[n - 1]
• যদি total_sum k দ্বারা বিভাজ্য নয়, তবে:
  • False রিটার্ন করুন
• count := 0, pos := -1
• i ০ থেকে n - 1 পর্যন্ত, করুন:
  • যদি pos -১ সমান হয়, তবে:
    • sub := 0
  • অন্যথায়:
    • sub := cumul_sum[pos]
  • যদি cumul_sum[i] - sub (total_sum / K) সমান হয়, তবে:
    • pos := i
    • count := count + 1
  • অন্যথায় যখন cumul_sum[i] - cumul_sum[pos] > (total_sum / K), তবে:
    • লুপ থেকে বের হোন
• True রিটার্ন করুন যখন count K সমান, অন্যথায় False

উদাহরণ

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:

def solve(nums, k):
    n = len(nums)
    cumul_sum = [0 for i in range(n)]
    cumul_sum[0] = nums[0]
    for i in range(1, n):
        cumul_sum[i] = cumul_sum[i - 1] + nums[i]
    total_sum = cumul_sum[n - 1]
    if total_sum % k != 0:
        return False
    count = 0
    pos = -1
    for i in range(n):
        if pos == -1:
            sub = 0
        else:
            sub = cumul_sum[pos]
        if cumul_sum[i] - sub == total_sum / k:
            pos = i
            count += 1
        elif cumul_sum[i] - cumul_sum[pos] > total_sum / k:
            break
    return count == k

nums = [2, 5, 3, 4, 7]
k = 3
print(solve(nums, k))

ইনপুট

[2, 5, 3, 4, 7], 3

আউটপুট

True