Dados dos arreglos arr[] y saltos[] que consisten en N enteros positivos, la tarea para cada elemento del arreglo arr[i] es encontrar el número mínimo de saltos necesarios para alcanzar un elemento de paridad opuesta. Los únicos saltos posibles desde cualquier elemento de array arr[i] son (i + jumps[i]) o (i – jumps[i]) .
Ejemplos:
Entrada: arr[] = {4, 2, 5, 2, 1}, jumps[] = {1, 2, 3, 1, 2}
Salida: 3 2 -1 1 -1
Explicación:
A continuación se muestran los pasos mínimos necesarios para cada elemento:
arr[4]: dado que salta[4] = 2, el único salto posible es (4 – salta[4]) = 2. Dado que arr[2] tiene la misma paridad que arr[4] y no más es posible saltar dentro del rango del índice de array, imprimir -1 .
arr[3]: como saltos[3] = 1, ambos saltos (3 + saltos[3]) = 4 o (3 – saltos[3]) = 2 son posibles. Dado que ambos elementos arr[2] y arr[4] son de paridad opuesta con arr[3], imprima 1 .
arr[2]: Imprimir -1 .
arr[1]:El único salto posible es (2 + saltos[2]). Dado que arr[3] tiene la misma paridad que arr[2] y los saltos mínimos necesarios desde arr[3] para alcanzar un elemento de array de paridad opuesta es 1, el número de saltos necesarios es 2.
arr[0]: arr[0 ] -> arr[3] -> (arr[4] o arr[2]). Por lo tanto, los saltos mínimos requeridos son 3.Entrada: arr[] = {4, 5, 7, 6, 7, 5, 4, 4, 6, 4}, salta[] = {1, 2, 3, 3, 5, 2, 7, 2, 4 , 1}
Salida: 1 1 2 2 1 1 -1 1 1 2
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array y realizar un recorrido primero en anchura para cada elemento de la array arr[i] , convirtiéndolo repetidamente en arr[i – jumps[i]] y arr[i + jumps [i]] , hasta que ocurra cualquier índice no válido, y después de cada conversión, verifique si el elemento de la array tiene la paridad opuesta al elemento anterior o no. Imprima el número mínimo de saltos necesarios para cada elemento de la array en consecuencia.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar BFS de múltiples fuentes para elementos de array pares e impares individualmente. Siga los pasos a continuación para resolver el problema:
- Inicialice un vector , digamos ans[] , para almacenar los saltos mínimos necesarios para que cada elemento de la array alcance un elemento de paridad opuesta.
- Inicialice una array de vectores , Adj[] para almacenar la lista de adyacencia del gráfico generado.
- Para cada par (i, j) de saltos válidos para cada índice, i de la array crea un gráfico invertido al inicializar los bordes como (j, i) .
- Realice un recorrido multifuente-BFS para elementos impares. Realice los siguientes pasos:
- Empuje todos los índices que contienen elementos de array impares a la cola y marque todos estos Nodes como visitados simultáneamente.
- Iterar hasta que la cola no esté vacía y realizar las siguientes operaciones:
- Haga estallar el Node presente al frente de la cola y verifique si alguno de los que ahora están conectados tiene la misma paridad o no. Si se determina que es cierto, actualice la distancia del Node secundario como la distancia 1 + del Node principal.
- Marque el Node secundario visitado y empújelo a la cola.
- Realice un recorrido multifuente-BFS para elementos pares de manera similar y almacene las distancias en ans[] .
- Después de completar los pasos anteriores, imprima los valores almacenados en ans[] como resultado.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
3 2 -1 1 -1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por shreyanshjain1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA