Minimum number of jumps to obtain an element of opposite parity | 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 Code
function bfs ( n , a , invGr , ans , parity ) { var q = [ ] ; var vis = Array ( n + 1 ) . fill ( 0 ) ; var dist = Array ( n + 1 ) . fill ( 0 ) ; for ( var i = 1 ; i <= n ; i ++ ) { if ( ( a [ i ] + parity ) & 1 ) { q . push ( i ) ; vis [ i ] = 1 ; } } while ( q . length != 0 ) { var v = q [ 0 ] ; q . shift ( ) ; invGr [ v ] . forEach ( u => { if ( ! vis [ u ] ) { dist [ u ] = dist [ v ] + 1 ; vis [ u ] = 1 ; if ( ( a [ u ] + parity ) % 2 == 0 ) { if ( ans [ u ] == - 1 ) ans [ u ] = dist [ u ] ; } q . push ( u ) ; } } ) ; } return ans ; } function minJumps ( a , jump , n ) { var invGr = Array . from ( Array ( n + 1 ) , ( ) => Array ( ) ) var ans = Array ( n + 1 ) . fill ( - 1 ) ; for ( var i = 1 ; i <= n ; i ++ ) { [ i + jump [ i ] , i - jump [ i ] ] . forEach ( ind => { if ( ind >= 1 && ind <= n ) { invGr [ ind ] . push ( i ) ; } } ) ; } ans = bfs ( n , a , invGr , ans , 0 ) ; ans = bfs ( n , a , invGr , ans , 1 ) ; for ( var i = 1 ; i <= n ; i ++ ) { document . write ( ans [ i ] + ' ' ) ; } } 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 ) ;