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