মান ল করুন l1 এবং l2 নামে দুটি তালিকা, আমাদের এদের সমান করতে হবে নিচের অপারেশন বারবার প্রয়োগ করে — একটি সাবলিস্ট বেছে নিন, এবং পুরো সাবলিস্টকে তার সম দিয়ে রিপ্লেস করুন। অবশেষে উপরের অপারেশন প্রয়োগ করে সম্ভাব্য সবচেয়ে বড় ফাইনাল লিস্টের আকার ফেরত দিন। যদি সমাধান নেই, -1 ফেরত দিন।
যদি ইনপুট হয় l1 = [1, 4, 7, 1, 2, 10], l2 = [5, 6, 1, 3, 10], তবে আউটপুট হবে ৪, কারণ নিচের অপারেশনগুলো করলে: l1-এর [1, 4] সাবলিস্ট নিলে [5, 7, 1, 2, 10], l1-এর [1, 2] নিলে [5, 7, 3, 10], l2-এর [6, 1] নিলে [5, 7, 3, 10]।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- i := l1-এর আকার - 1, j := l2-এর আকার - 1, res := 0
- যখন i >= 0 এবং j >= 0:
- যদি l1[i] == l2[j], res := res + 1, i := i - 1, j := j - 1
- অন্যথায় যদি l1[i] < l2[j], যদি i > 0, l1[i-1] := l1[i-1] + l1[i], i := i - 1
- অন্যথায় যদি l1[i] > l2[j], যদি j > 0, l2[j-1] := l2[j-1] + l2[j], j := j - 1
- যদি i == -1 এবং j == -1 হয়, res ফেরত দিন, অন্যথায় -1 ফেরত দিন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
class Solution: def solve(self, l1, l2): i, j, res = len(l1) - 1, len(l2) - 1, 0 while i >= 0 and j >= 0: if l1[i] == l2[j]: res, i, j = res + 1, i - 1, j - 1 elif l1[i] < l2[j]: if i > 0: l1[i - 1] += l1[i] i -= 1 elif l1[i] > l2[j]: if j > 0: l2[j - 1] += l2[j] j -= 1 return res if i == -1 and j == -1 else -1 ob = Solution() l1 = [1, 4, 7, 1, 2, 10] l2 = [5, 6, 1, 3, 10] print(ob.solve(l1, l2))
ইনপুট
[1, 4, 7, 1, 2, 10], [5, 6, 1, 3, 10]
আউটপুট
4
