Minimum number of jumps to obtain an element of opposite parity

0 0 11 minutes read

Given two arrays arr[] and jumps[] consisting of N positive integers, the task for each array element arr[i] is to find the minimum number of jumps required to reach an element of opposite parity. The only possible jumps from any array element arr[i] are (i + jumps[i]) or (i – jumps[i]).

Examples:

Input: arr[] = {4, 2, 5, 2, 1}, jumps[] = {1, 2, 3, 1, 2}
Output: 3 2 -1 1 -1
Explanation:
Below are the minimum steps required for each element:
arr[4]: Since jumps[4] = 2, the only possible jump is (4 – jumps[4]) = 2. Since arr[2] is of same parity as arr[4] and no further jump within the range of array indice is possible, print -1.
arr[3]: Since jumps[3] = 1, both the jumps (3 + jumps[3]) = 4 or (3 – jumps[3]) = 2 are possible. Since both the elements arr[2] and arr[4] are of opposite parity with arr[3], print 1.
arr[2]: Print -1.
arr[1]: Only possible jump is (2 + jumps[2]). Since arr[3] is of same parity as arr[2] and minimum jumps required from arr[3] to reach an array element of opposite parity is 1, the number of jumps required is 2.
arr[0]: arr[0] -> arr[3] -> (arr[4] or arr[2]). Therefore, minimum jumps required is 3.

Input: arr[] = {4, 5, 7, 6, 7, 5, 4, 4, 6, 4}, jumps[] = {1, 2, 3, 3, 5, 2, 7, 2, 4, 1}
Output: 1 1 2 2 1 1 -1 1 1 2

Naive Approach: The simplest approach is to solve the problem is to traverse the array and perform Breadth-First Traversal for each array element arr[i], by repeatedly converting to arr[i – jumps[i]] and arr[i + jumps[i]], until any invalid index occurs, and after each conversion, check if the array element is of opposite parity to the previous element or not. Print the minimum number of jumps required for each array element accordingly.

Time Complexity: O(N²)
Auxiliary Space: O(N)

Efficient Approach: To optimize the above approach, the idea is to use multi-source BFS for even and odd array elements individually. Follow the steps below to solve the problem:

Initialize a vector, say ans[], to store the minimum jumps required for each array element to reach an element of opposite parity.
Initialize an array of vectors, Adj[] to store the adjacency list of the graph generated.
For every pair (i, j) of valid jumps for each index, i of the array create an inverted graph by initializing edges as (j, i).
Perform multisource-BFS traversal for odd elements. Perform the following steps:
- Push all indices that contains odd array elements, into the queue and mark all these nodes as visited simultaneously.
- Iterate until queue is non-empty and perform the following operations:
  - Pop the node present at the front of the queue and check if any of its now connected to it is of same parity or not. If found to be true, update the distance of the child node as the 1 + distance of parent node.
  - Mark the child node visited and push it into the queue.
Perform multisource-BFS traversal for even elements similarly and store the distances in ans[].
After completing the above steps, print the values stored in ans[] as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Bfs for odd numbers are source
void bfs(int n, vector<int>& a,
         vector<int> invGr[],
         vector<int>& ans, int parity)
{
    // Initialize queue
    queue<int> q;
 
    // Stores for each node, the nodes
    // visited and their distances
    vector<int> vis(n + 1, 0);
    vector<int> dist(n + 1, 0);
 
    // Push odd and even numbers
    // as sources to the queue
 
    // If parity is 0 -> odd
    // Otherwise -> even
    for (int i = 1; i <= n; i++) {
        if ((a[i] + parity) & 1) {
            q.push(i);
            vis[i] = 1;
        }
    }
 
    // Perform multi-source bfs
    while (!q.empty()) {
 
        // Extract the front element
        // of the queue
        int v = q.front();
        q.pop();
 
        // Traverse nodes connected
        // to the current node
        for (int u : invGr[v]) {
 
            // If u is not visited
            if (!vis[u]) {
 
                dist[u] = dist[v] + 1;
                vis[u] = 1;
 
                // If element with opposite
                // parity is obtained
                if ((a[u] + parity) % 2 == 0) {
                    if (ans[u] == -1)
 
                        // Store its distance from
                        // source in ans[]
                        ans[u] = dist[u];
                }
 
                // Push the current neighbour
                // to the queue
                q.push(u);
            }
        }
    }
}
 
// Function to find the minimum jumps
// required by each index to reach
// element of opposite parity
void minJumps(vector<int>& a,
              vector<int>& jump, int n)
{
    // Initialise Inverse Graph
    vector<int> invGr[n + 1];
 
    // Stores the result for each index
    vector<int> ans(n + 1, -1);
 
    for (int i = 1; i <= n; i++) {
 
        // For the jumped index
        for (int ind : { i + jump[i],
                         i - jump[i] }) {
 
            // If the ind is valid then
            // add reverse directed edge
            if (ind >= 1 and ind <= n) {
                invGr[ind].push_back(i);
            }
        }
    }
 
    // Multi-source bfs with odd
    // numbers as source by passing 0
    bfs(n, a, invGr, ans, 0);
 
    // Multi-source bfs with even
    // numbers as source by passing 1
    bfs(n, a, invGr, ans, 1);
 
    // Print the answer
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << ' ';
    }
}
 
// Driver Code
int main()
{
    vector<int> arr = { 0, 4, 2, 5, 2, 1 };
    vector<int> jump = { 0, 1, 2, 3, 1, 2 };
 
    int N = arr.size();
 
    minJumps(arr, jump, N - 1);
 
    return 0;
}

Java

// Java program for above approach
import java.util.*;
import java.lang.*;
 
class Gfg
{
 
  // Bfs for odd numbers are source
  static void bfs(int n, int[] a,
                  ArrayList<ArrayList<Integer>> invGr,
                  int[] ans, int parity)
  {
 
    // Initialize queue
    Queue<Integer> q = new LinkedList<>();
 
    // Stores for each node, the nodes
    // visited and their distances
    int[] vis = new int[n + 1];
    int[] dist = new int[n + 1];
 
    // Push odd and even numbers
    // as sources to the queue
 
    // If parity is 0 -> odd
    // Otherwise -> even
    for (int i = 1; i <= n; i++) {
      if (((a[i] + parity) & 1) != 0) {
        q.add(i);
        vis[i] = 1;
      }
    }
 
    // Perform multi-source bfs
    while (!q.isEmpty()) {
 
      // Extract the front element
      // of the queue
      int v = q.peek();
      q.poll();
 
      // Traverse nodes connected
      // to the current node
      for (Integer u : invGr.get(v)) {
 
        // If u is not visited
        if (vis[u] == 0) {
 
          dist[u] = dist[v] + 1;
          vis[u] = 1;
 
          // If element with opposite
          // parity is obtained
          if ((a[u] + parity) % 2 == 0) {
            if (ans[u] == -1)
 
              // Store its distance from
              // source in ans[]
              ans[u] = dist[u];
          }
 
          // Push the current neighbour
          // to the queue
          q.add(u);
        }
      }
    }
  }
 
  // Function to find the minimum jumps
  // required by each index to reach
  // element of opposite parity
  static void minJumps(int[] a,
                       int[] jump, int n)
  {
 
    // Initialise Inverse Graph
    ArrayList<ArrayList<Integer>> invGr = new ArrayList<>();
 
    for(int i = 0; i <= n; i++)
      invGr.add(new ArrayList<Integer>());
 
    // Stores the result for each index
    int[] ans = new int[n + 1];
    Arrays.fill(ans, -1);
 
    for (int i = 1; i <= n; i++) 
    {
 
      // For the jumped index
      // If the ind is valid then
      // add reverse directed edge
      if (i+ jump[i] >= 1 && i+jump[i] <= n) {
        invGr.get(i+ jump[i]).add(i);
      }
      if (i-jump[i] >= 1 && i-jump[i] <= n) {
        invGr.get(i- jump[i]).add(i);
      }
    }
 
    // Multi-source bfs with odd
    // numbers as source by passing 0
    bfs(n, a, invGr, ans, 0);
 
    // Multi-source bfs with even
    // numbers as source by passing 1
    bfs(n, a, invGr, ans, 1);
 
    // Print the answer
    for (int i = 1; i <= n; i++) 
    {
      System.out.print(ans[i] + " ");
    }
  }
 
  // Driver function
  public static void main (String[] args)
  {
    int[] arr = { 0, 4, 2, 5, 2, 1 };
    int[] jump = { 0, 1, 2, 3, 1, 2 };
 
    int N = arr.length;
 
    minJumps(arr, jump, N - 1);
  }
}
 
// This code is contributed by offbeat

Python3

# Python3 program for the above approach
  
# Bfs for odd numbers are source
def bfs(n, a, invGr, ans, parity):
     
    # Initialize queue
    q = []
     
    # Stores for each node, the nodes
    # visited and their distances
    vis = [0 for i in range(n + 1)]
    dist = [0 for i in range(n + 1)]
  
    # Push odd and even numbers
    # as sources to the queue
  
    # If parity is 0 -> odd
    # Otherwise -> even
    for i in range(1, n + 1):
        if ((a[i] + parity) & 1):
            q.append(i)
            vis[i] = 1
             
    # Perform multi-source bfs
    while (len(q) != 0):
         
        # Extract the front element
        # of the queue
        v = q[0]
        q.pop(0)
  
        # Traverse nodes connected
        # to the current node
        for u in invGr[v]:
  
            # If u is not visited
            if (not vis[u]):
                dist[u] = dist[v] + 1
                vis[u] = 1
  
                # If element with opposite
                # parity is obtained
                if ((a[u] + parity) % 2 == 0):
                    if (ans[u] == -1):
  
                        # Store its distance from
                        # source in ans[]
                        ans[u] = dist[u]
  
                # Push the current neighbour
                # to the queue
                q.append(u)
  
# Function to find the minimum jumps
# required by each index to reach
# element of opposite parity
def minJumps(a, jump, n):
 
    # Initialise Inverse Graph
    invGr = [[] for i in range(n + 1)]
  
    # Stores the result for each index
    ans = [-1 for i in range(n + 1)]
     
    for i in range(1, n + 1):
  
        # For the jumped index
        for ind in [i + jump[i], i - jump[i]]:
  
            # If the ind is valid then
            # add reverse directed edge
            if (ind >= 1 and ind <= n):
                invGr[ind].append(i)
  
    # Multi-source bfs with odd
    # numbers as source by passing 0
    bfs(n, a, invGr, ans, 0)
  
    # Multi-source bfs with even
    # numbers as source by passing 1
    bfs(n, a, invGr, ans, 1)
  
    # Print the answer
    for i in range(1, n + 1):
        print(str(ans[i]), end = ' ')
         
# Driver Code
if __name__=='__main__':
     
    arr = [ 0, 4, 2, 5, 2, 1 ]
    jump = [ 0, 1, 2, 3, 1, 2 ]
  
    N = len(arr)
  
    minJumps(arr, jump, N - 1)
     
# This code is contributed by pratham76

C#

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
  // Bfs for odd numbers are source 
  static void bfs(int n, int[] a, List<List<int>> invGr, int[] ans, int parity) 
  { 
 
    // Initialize queue 
    Queue<int> q = new Queue<int>(); 
 
    // Stores for each node, the nodes 
    // visited and their distances 
    int[] vis = new int[n + 1]; 
    int[] dist = new int[n + 1]; 
 
    // Push odd and even numbers 
    // as sources to the queue 
 
    // If parity is 0 -> odd 
    // Otherwise -> even 
    for (int i = 1 ; i <= n ; i++) { 
      if (((a[i] + parity) & 1) != 0) { 
        q.Enqueue(i); 
        vis[i] = 1; 
      }
    } 
 
    // Perform multi-source bfs 
    while (q.Count > 0) { 
 
      // Extract the front element 
      // of the queue 
      int v = q.Peek(); 
      q.Dequeue();
 
      // Traverse nodes connected 
      // to the current node 
      foreach (int u in invGr[v]) { 
 
        // If u is not visited 
        if (vis[u] == 0) { 
 
          dist[u] = dist[v] + 1; 
          vis[u] = 1; 
 
          // If element with opposite 
          // parity is obtained 
          if ((a[u] + parity) % 2 == 0) { 
            if (ans[u] == -1){
 
              // Store its distance from 
              // source in ans[] 
              ans[u] = dist[u]; 
            }
          }
 
          // Push the current neighbour 
          // to the queue 
          q.Enqueue(u); 
        } 
      } 
    } 
  } 
 
  // Function to find the minimum jumps 
  // required by each index to reach 
  // element of opposite parity 
  static void minJumps(int[] a, int[] jump, int n) 
  { 
 
    // Initialise Inverse Graph 
    List<List<int>> invGr = new List<List<int>>(); 
 
    for(int i = 0 ; i <= n ; i++) 
      invGr.Add(new List<int>()); 
 
    // Stores the result for each index 
    int[] ans = new int[n + 1]; 
    for(int i = 0 ; i <= n ; i++){
      ans[i] = -1;
    }
 
    for (int i = 1 ; i <= n ; i++) 
    { 
 
      // For the jumped index 
      // If the ind is valid then 
      // add reverse directed edge 
      if (i+ jump[i] >= 1 && i+jump[i] <= n) { 
        invGr[i+ jump[i]].Add(i); 
      } 
      if (i-jump[i] >= 1 && i-jump[i] <= n) { 
        invGr[i- jump[i]].Add(i); 
      }
    } 
 
    // Multi-source bfs with odd 
    // numbers as source by passing 0 
    bfs(n, a, invGr, ans, 0); 
 
    // Multi-source bfs with even 
    // numbers as source by passing 1 
    bfs(n, a, invGr, ans, 1); 
 
    // Print the answer 
    for (int i = 1 ; i <= n ; i++) 
    { 
      Console.Write(ans[i] + " "); 
    } 
  }
 
  // Driver code
  public static void Main(string[] args){
 
    int[] arr = new int[]{ 0, 4, 2, 5, 2, 1 }; 
    int[] jump = new int[]{ 0, 1, 2, 3, 1, 2 }; 
 
    int N = arr.Length; 
 
    minJumps(arr, jump, N - 1); 
  }
}
 
// This code is contributed by subhamgoyal2014.

Javascript

<script>
 
// JavaScript program for the above approach
 
// Bfs for odd numbers are source
function bfs(n, a, invGr, ans, parity)
{
    // Initialize queue
    var q = [];
 
    // Stores for each node, the nodes
    // visited and their distances
    var vis = Array(n+1).fill(0);
    var dist = Array(n+1).fill(0);
 
    // Push odd and even numbers
    // as sources to the queue
 
    // If parity is 0 -> odd
    // Otherwise -> even
    for (var i = 1; i <= n; i++) {
        if ((a[i] + parity) & 1) {
            q.push(i);
            vis[i] = 1;
        }
    }
 
    // Perform multi-source bfs
    while (q.length!=0) {
 
        // Extract the front element
        // of the queue
        var v = q[0];
        q.shift();
 
        // Traverse nodes connected
        // to the current node
        invGr[v].forEach(u => {
             
 
            // If u is not visited
            if (!vis[u]) {
 
                dist[u] = dist[v] + 1;
                vis[u] = 1;
 
                // If element with opposite
                // parity is obtained
                if ((a[u] + parity) % 2 == 0) {
                    if (ans[u] == -1)
 
                        // Store its distance from
                        // source in ans[]
                        ans[u] = dist[u];
                }
 
                // Push the current neighbour
                // to the queue
                q.push(u);
            }
        });
    }
    return ans;
}
 
// Function to find the minimum jumps
// required by each index to reach
// element of opposite parity
function minJumps(a, jump, n)
{
    // Initialise Inverse Graph
    var invGr = Array.from(Array(n+1), ()=>Array())
 
    // Stores the result for each index
    var ans = Array(n + 1).fill(-1);
 
    for (var i = 1; i <= n; i++) {
 
        // For the jumped index
        [i + jump[i], i - jump[i]].forEach(ind => {
             
 
            // If the ind is valid then
            // add reverse directed edge
            if (ind >= 1 && ind <= n) {
                invGr[ind].push(i);
            }
        });
    }
 
    // Multi-source bfs with odd
    // numbers as source by passing 0
    ans = bfs(n, a, invGr, ans, 0);
 
    // Multi-source bfs with even
    // numbers as source by passing 1
    ans = bfs(n, a, invGr, ans, 1);
 
    // Print the answer
    for (var i = 1; i <= n; i++) {
        document.write( ans[i] + ' ');
    }
}
 
// Driver Code
var arr = [0, 4, 2, 5, 2, 1];
var jump = [0, 1, 2, 3, 1, 2];
var N = arr.length;
minJumps(arr, jump, N - 1);
 
</script>

Output:

3 2 -1 1 -1

Time Complexity: O(N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!