পাইথনে ভিন্ন সমতা সম্পন্ন মান পর্যন্ত ন্যূনতম জাম্প খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যার তালিকা nums দেওয়া আছে। এখানে আমরা সূচক i থেকে i + nums[i] বা i - nums[i] সূচকে যেতে পারি (যদি সেগুলি তালিকার মধ্যে থাকে)। আমাদের লক্ষ্য হল ইনপুটের ক্রম অপরিবর্তিত রেখে ভিন্ন সমতা (parity) সম্পন্ন অন্য একটি মানের কাছে যেতে ন্যূনতম কতগুলো জাম্প লাগবে তা বের করা। যদি ভিন্ন সমতা সম্পন্ন কোনো সংখ্যার কাছে যাওয়া সম্ভব না হয়, তবে আউটপুট হবে -1।

উদাহরণস্বরূপ, ইনপুট numbers = [7, 3, 4, 5, 6, 9, 6, 7] হলে আউটপুট হবে [-1, 1, 2, -1, -1, -1, 1, -1]।

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

bfs() ফাংশন সংজ্ঞায়িত করুন যা একটি সূচক i নেবে:
- q := একটি ডবল-এন্ডেড কিউ যেখানে প্রথমে (i, 0) জোড়া রাখা হবে
- seen := একটি নতুন সেট
- যখন q খালি নয়:
  - (j, d) := q-র বামপাশের উপাদান বের করুন এবং সেটি মুছে দিন
  - j কে seen তে যোগ করুন
  - যদি (nums[i] + nums[j]) % 2 != 0 হয়, তবে d ফেরত দিন
  - k এর জন্য [j + nums[j], j - nums[j]] তে:
    - যদি 0 <= k < len(nums) এবং k seen-এ না থাকে, তবে (k, d + 1) কে q-র ডানে যোগ করুন
- 10^10 ফেরত দিন (অনাপন্ন সigte নির্দেশ করতে)
মূল পদ্ধতিতে:
- ans := একটি নতুন তালিকা
- i = 0 থেকে len(nums)-1 পর্যন্ত:
  - seen := new set
  - x := bfs(i)
  - ans তে x যোগ করুন যদি x < 10^10, অন্যথায় -1 যোগ করুন
- ans ফেরত দিন

উদাহরণ

from collections import deque

class Solution:
    def solve(self, nums):
        def bfs(i):
            q = deque([(i, 0)])
            seen = set()
            while q:
                j, d = q.popleft()
                seen.add(j)
                if (nums[i] + nums[j]) % 2:
                    return d
                for k in [j + nums[j], j - nums[j]]:
                    if 0 <= k < len(nums) and k not in seen:
                        q.append((k, d + 1))
            return 10 ** 10

        ans = []
        for i in range(len(nums)):
            seen = set()
            x = bfs(i)
            ans.append(x if x < 10 ** 10 else -1)
        return ans

ob = Solution()
print(ob.solve([7, 3, 4, 5, 6, 9, 6, 7]))

ইনপুট

numbers = [7, 3, 4, 5, 6, 9, 6, 7]

আউটপুট

[-1, 1, 2, -1, -1, -1, 1, -1]