পাইথনে তালিকা ইনডেক্স আপডেট করে টার্গেট পাওয়া যায় কিনা যাচাই

target নামক একটি তালিকা দেওয়া আছে। একই দৈর্ঘ্যের X তালিকা বিবেচনা করুন যা ১ দিয়ে ভরা। আমরা যেকোনো ইন্ডেক্স i-এ X[i] কে X-এর বর্তমান যোগফলে আপডেট করতে পারি। এটি যেকোনো বার করা যায়। চূড়ান্তে X কে target-এ রূপান্তর করা সম্ভব কিনা তা যাচাই করতে হবে।

উদাহরণ: target = [5, 9, 3] হলে আউটপুট True। কারণ X=[1,1,1] -> যোগফল ৩ -> [1,1,3] -> যোগফল ৫ -> [5,1,3] -> যোগফল ৯ -> [5,9,3]।

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

• যদি একক উপাদান থাকে তবে সেটি ১ কিনা যাচাই করুন
• ম্যাক্স হিপ (নেগেটিভ ভ্যালু) ব্যবহার করুন
• সর্বোচ্চ উপাদান বের করে বাকি যোগফল d = sum - x বের করুন
• x2 := x % d (যদি d>1) অন্যথায় ১
• সাম্য বজায় না থাকা পর্যন্ত লুপ চালান
• সব -1 হলে True ফেরত দিন

উদাহরণ কোড

class Solution:
    def solve(self, nums):
        if len(nums) == 1:
            return nums == [1]
        from heapq import heapify, heappop, heappush
        q = [-x for x in nums]
        heapify(q)
        s = sum(nums)
        ok = True
        while ok:
            x = -heappop(q)
            d = s - x
            x2 = x % d if d > 1 else 1
            s += x2 - x
            ok = x != x2
            x = x2
            heappush(q, -x)
        return all(x == -1 for x in q)

ob = Solution()
target = [5, 9, 3]
print(ob.solve(target))

ইনপুট

[5, 9, 3]

আউটপুট

True