पायथन में अलग पैरिटी वाले मान तक पहुंचने के लिए आवश्यक न्यूनतम जंप ढूंढने का प्रोग्राम

मान लीजिए हमारे पास संख्याओं की एक सूची है जिसे nums कहा जाता है। यहां हम इंडेक्स i से i + numbers[i] या i - numbers[i] पर जा सकते हैं, बशर्ते वे मान सूची में मौजूद हों। हमें इनपुट में क्रम को बरकरार रखते हुए, अलग पैरिटी (सम/विषम) वाले किसी अन्य मान तक पहुंचने के लिए आवश्यक न्यूनतम जंप की संख्या ढूंढनी है। यदि हम अलग पैरिटी वाली किसी अन्य संख्या तक नहीं पहुंच सकते, तो इसे -1 पर सेट किया जाता है।

उदाहरण के लिए, यदि इनपुट numbers = [7, 3, 4, 5, 6, 9, 6, 7] है, तो आउटपुट [-1, 1, 2, -1, -1, -1, 1, -1] होगा।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

1. BFS फ़ंक्शन परिभाषित करें: यह फ़ंक्शन एक शुरुआती इंडेक्स i लेगा और ब्रेडथ-फर्स्ट सर्च का उपयोग करके न्यूनतम जंप ढूंढेगा।
   • एक डबल-एंडेड क्यू (deque) बनाएं जिसमें (i, 0) जोड़ा हो (इंडेक्स और दूरी)।
   • देखे गए इंडेक्स को ट्रैक करने के लिए एक सेट बनाएं।
   • जब तक क्यू खाली न हो:
     • क्यू से सबसे बायां एलिमेंट (j, d) निकालें।
     • j को देखे गए सेट में जोड़ें।
     • यदि (nums[i] + nums[j]) % 2 शून्येतर है (यानी पैरिटी अलग है), तो d लौटाएं।
     • अगले संभावित जंप के लिए k की गणना करें: j + nums[j] और j - nums[j]।
     • यदि k वैध सीमा (0 <= k < len(nums)) में है और पहले नहीं देखा गया, तो (k, d+1) को क्यू के दाएं छोर पर जोड़ें।
   • यदि कोई वैध पथ नहीं मिलता, तो एक बड़ी संख्या (10^10) लौटाएं।
2. मुख्य विधि:
   • एक खाली सूची ans बनाएं।
   • प्रत्येक इंडेक्स i के लिए 0 से len(nums)-1 तक:
     • देखे गए सेट को रीसेट करें।
     • bfs(i) कॉल करें और परिणाम x प्राप्त करें।
     • यदि x < 10^10 है तो ans में x जोड़ें, अन्यथा -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]