Minimum Jumps Required to Reach a Value with Different Parity in Python

Suppose, we are provided with a list of numbers called nums. Here we can jump to index i + numbers[i] or to i − numbers[i] from index i if the values exist in the list. So we have to find the number of jumps required at least to reach another value with different parity keeping the order in the input unchanged. If we cannot reach another number with different parity, it is set to −1.

So, if the input is like numbers = [7, 3, 4, 5, 6, 9, 6, 7], then the output will be [−1, 1, 2, −1, −1, −1, 1, −1].

To solve this, we will follow these steps −

• Define a function bfs() . This will take i

  • q := a new double ended queue with a pair (i, 0)

  • seen := a new set

  • while q is not empty, do

    • (j, d) := left most element of q and delete the leftmost item from q

    • add j into seen

    • if (nums[i] + nums[j]) mod 2 is non−zero, then

      • return d

    • for each k in [j + nums[j], j − nums[j]], do

      • if 0 <= k < size of nums and k is not in seen, then

        • insert (k, d + 1) at the right end of q

  • return 10^10

• From the main method do the following −

• ans := a new list

• for i in range 0 to size of nums, do

  • seen := a new set

  • x := bfs(i)

  • append x in ans when x < 10^10 otherwise append −1

• return ans

Let us see the following implementation to get better understanding −

Example

 Live Demo

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]))

Input

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

Output

[−1, 1, 2, −1, −1, −1, 1, −1]