Dada una array arr[] de N enteros positivos y dos enteros positivos S y K , la tarea es alcanzar la posición de la array cuyo valor es K del índice S . Solo podemos pasar del índice actual i al índice (i + arr[i]) o (i – arr[i]) . Si hay una forma de alcanzar la posición de la array cuyo valor es K , imprima «Sí» , de lo contrario, imprima «No» .
Ejemplos:
Entrada: arr[] = {4, 2, 3, 0, 3, 1, 2}, S = 5, K = 0.
Salida: Sí
Explicación:
Inicialmente estamos parados en el índice 5 que es el elemento 1, por lo que podemos mover un paso adelante o atrás. Por lo tanto, todas las formas posibles de llegar al índice 3 con valor 0 son:
índice 5 -> índice 4 -> índice 1 -> índice 3
índice 5 -> índice 6 -> índice 4 -> índice 1 -> índice 3. Dado que es posible alcanzar el índice 3 nuestra salida es sí.Entrada: arr[] = {0, 3, 2, 1, 2}, S = 2, K = 3
Salida: No
Explicación:
No hay forma de alcanzar el índice 1 con el valor 3.
Método 1: uso de BFS El enfoque de búsqueda en amplitud (BFS) se analiza a continuación:
- Considere el índice de inicio S como el Node de origen e insértelo en la cola .
- Mientras la cola no esté vacía, haga lo siguiente:
- Haga estallar el elemento de la parte superior de la cola, digamos temp .
- Si ya se visitó la temperatura o si la array está fuera del índice enlazado, vaya al paso 1.
- De lo contrario, márquelo como visitado.
- Ahora, si temp es el índice de la array cuyo valor es K , imprima «Sí» .
- De lo contrario, tome dos destinos posibles de temp a (temp + arr[temp]) , (temp – arr[temp]) y empújelo a la cola.
- Si no se alcanza el índice con el valor K después de los pasos anteriores, imprima «No» .
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 approach to check if traversal
// is possible or not
bool check(int arr[], int& s_start,
int start, bool visited[],
int size, int K)
{
queue<int> q;
// Push start index into queue
q.push(start);
// Until queue is not empty
while (!q.empty()) {
// Top element of queue
int front = q.front();
// Pop the topmost element
q.pop();
// mark as visited
visited[front] = true;
if (arr[front] == K
&& front != s_start) {
return true;
}
// Check for i + arr[i]
if (front + arr[front] >= 0
&& front + arr[front] < size
&& visited[front + arr[front]]
== false) {
q.push(front + arr[front]);
}
// Check for i - arr[i]
if (front - arr[front] >= 0
&& front - arr[front] < size
&& visited[front - arr[front]]
== false) {
q.push(front - arr[front]);
}
}
return false;
}
// Function to check if index with value
// K can be reached or not
void solve(int arr[], int n, int start,
int K)
{
// Initialize visited array
bool visited[n] = { false };
// BFS Traversal
bool ans = check(arr, start, start,
visited, n, K);
// Print the result
if (ans)
cout << "Yes";
else
cout << "No";
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 3, 0, 2, 1, 2 };
// Given start and end
int start = 2;
int K = 0;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
solve(arr, N, start, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// BFS approach to check if traversal
// is possible or not
static boolean check(int arr[], int s_start, int start,
boolean visited[], int size, int K)
{
Queue<Integer> q = new LinkedList<Integer>();
// Push start index into queue
q.add(start);
// Until queue is not empty
while (!q.isEmpty())
{
// Top element of queue
int front = q.peek();
// Pop the topmost element
q.remove();
// mark as visited
visited[front] = true;
if (arr[front] == K && front != s_start)
{
return true;
}
// Check for i + arr[i]
if (front + arr[front] >= 0 &&
front + arr[front] < size &&
visited[front + arr[front]] == false)
{
q.add(front + arr[front]);
}
// Check for i - arr[i]
if (front - arr[front] >= 0 &&
front - arr[front] < size &&
visited[front - arr[front]] == false)
{
q.add(front - arr[front]);
}
}
return false;
}
// Function to check if index with value
// K can be reached or not
static void solve(int arr[], int n, int start, int K)
{
// Initialize visited array
boolean visited[] = new boolean[n];
// BFS Traversal
boolean ans = check(arr, start, start,
visited, n, K);
// Print the result
if (ans)
System.out.print("Yes");
else
System.out.print("No");
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 3, 0, 2, 1, 2 };
// Given start and end
int start = 2;
int K = 0;
int N = arr.length;
// Function Call
solve(arr, N, start, K);
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program for the above approach
# BFS approach to check if traversal
# is possible or not
def check(arr, s_start, start,
visited, size, K):
q = []
# Push start index into queue
q.append(start)
# Until queue is not empty
while (len(q) != 0):
# Top element of queue
front = q[-1]
# Pop the topmost element
q.pop(0)
# Mark as visited
visited[front] = True
if (arr[front] == K and front != s_start):
return True
# Check for i + arr[i]
if (front + arr[front] >= 0 and
front + arr[front] < size and
visited[front + arr[front]] == False):
q.append(front + arr[front])
# Check for i - arr[i]
if (front - arr[front] >= 0 and
front - arr[front] < size and
visited[front - arr[front]] == False):
q.append(front - arr[front])
return False
# Function to check if index with value
# K can be reached or not
def solve(arr, n, start, K):
# Initialize visited array
visited = [False for i in range(n)]
# BFS Traversal
ans = check(arr, start, start,
visited, n, K)
# Print the result
if (ans):
print('Yes')
else:
print('No')
# Driver Code
if __name__=="__main__":
# Given array arr[]
arr = [ 3, 0, 2, 1, 2 ]
# Given start and end
start = 2
K = 0
N = len(arr)
# Function Call
solve(arr, N, start, K)
# This code is contributed by rutvik_56
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// BFS approach to check if traversal
// is possible or not
static bool check(int []arr, int s_start, int start,
bool []visited, int size, int K)
{
Queue<int> q = new Queue<int>();
// Push start index into queue
q.Enqueue(start);
// Until queue is not empty
while (q.Count != 0)
{
// Top element of queue
int front = q.Peek();
// Pop the topmost element
q.Dequeue();
// mark as visited
visited[front] = true;
if (arr[front] == K && front != s_start)
{
return true;
}
// Check for i + arr[i]
if (front + arr[front] >= 0 &&
front + arr[front] < size &&
visited[front + arr[front]] == false)
{
q.Enqueue(front + arr[front]);
}
// Check for i - arr[i]
if (front - arr[front] >= 0 &&
front - arr[front] < size &&
visited[front - arr[front]] == false)
{
q.Enqueue(front - arr[front]);
}
}
return false;
}
// Function to check if index with value
// K can be reached or not
static void solve(int []arr, int n, int start,
int K)
{
// Initialize visited array
bool []visited = new bool[n];
// BFS Traversal
bool ans = check(arr, start, start,
visited, n, K);
// Print the result
if (ans)
Console.Write("Yes");
else
Console.Write("No");
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 3, 0, 2, 1, 2 };
// Given start and end
int start = 2;
int K = 0;
int N = arr.Length;
// Function call
solve(arr, N, start, K);
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// JavaScript program for the above approach
// BFS approach to check if traversal
// is possible or not
function check(arr, s_start, start, visited, size, K)
{
let q = [];
// Push start index into queue
q.push(start);
// Until queue is not empty
while (q.length > 0)
{
// Top element of queue
let front = q[0];
// Pop the topmost element
q.shift();
// mark as visited
visited[front] = true;
if (arr[front] == K && front != s_start)
{
return true;
}
// Check for i + arr[i]
if (front + arr[front] >= 0 &&
front + arr[front] < size &&
visited[front + arr[front]] == false)
{
q.push(front + arr[front]);
}
// Check for i - arr[i]
if (front - arr[front] >= 0 &&
front - arr[front] < size &&
visited[front - arr[front]] == false)
{
q.push(front - arr[front]);
}
}
return false;
}
// Function to check if index with value
// K can be reached or not
function solve(arr, n, start, K)
{
// Initialize visited array
let visited = new Array(n);
// BFS Traversal
let ans = check(arr, start, start,
visited, n, K);
// Print the result
if (ans)
document.write("Yes");
else
document.write("No");
}
// Given array arr[]
let arr = [ 3, 0, 2, 1, 2 ];
// Given start and end
let start = 2;
let K = 0;
let N = arr.length;
// Function Call
solve(arr, N, start, K);
</script>
Producción
No
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Método 2: uso de DFS: el enfoque de búsqueda en profundidad (DFS) se analiza a continuación:
- Inicialice una array visitada [] para marcar el vértice visitado como verdadero.
- Comience con el índice de inicio S y explore otros índices en profundidad usando recursion .
- En cada llamada recursiva comprobamos si ese índice es válido o no visitado anteriormente. Si no es así, devolvemos falso.
- De lo contrario, si ese valor de índice es K , devolvemos verdadero.
- De lo contrario, marque ese índice como visitado y procese recursivamente para i + arr[i] e i – arr[i] del índice actual i.
- Si alguna de las llamadas recursivas devuelve verdadero, esto significa que es posible alcanzar el índice con el valor K e imprimimos «Sí» . De lo contrario, imprime «No» .
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;
// DFS approach to check if traversal
// is possible or not
bool check(int arr[], int& s_start,
int start, bool visited[],
int size, int K)
{
// Base cases
if (start < 0 || start >= size
|| visited[start]) {
return false;
}
// Check if start index value K
if (arr[start] == K
&& start != s_start) {
return true;
}
// Mark as visited
visited[start] = true;
// Check for both i + arr[i]
// and i - arr[i] recursively
return (check(arr, s_start,
start + arr[start],
visited, size, K)
|| check(arr, s_start,
start - arr[start],
visited, size, K));
}
// Function to check if index with value
// K can be reached or not
void solve(int arr[], int n, int start,
int K)
{
// Initialize visited array
bool visited[n] = { false };
// DFS Traversal
bool ans = check(arr, start, start,
visited, n, K);
// Print the result
if (ans)
cout << "Yes";
else
cout << "No";
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 3, 0, 2, 1, 2 };
// Given start and end
int start = 2;
int K = 0;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
solve(arr, N, start, K);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG{
// DFS approach to check if traversal
// is possible or not
public static boolean check(int[] arr, int s_start,
int start, boolean[] visited,
int size, int K)
{
// Base cases
if (start < 0 || start >= size ||
visited[start])
{
return false;
}
// Check if start index value K
if (arr[start] == K &&
start != s_start)
{
return true;
}
// Mark as visited
visited[start] = true;
// Check for both i + arr[i]
// and i - arr[i] recursively
return (check(arr, s_start,
start + arr[start],
visited, size, K) ||
check(arr, s_start,
start - arr[start],
visited, size, K));
}
// Function to check if index with value
// K can be reached or not
public static void solve(int[] arr, int n,
int start, int K)
{
// Initialize visited array
boolean[] visited = new boolean[n];
Arrays.fill(visited, false);
// DFS Traversal
boolean ans = check(arr, start, start,
visited, n, K);
// Print the result
if (ans)
System.out.print("Yes");
else
System.out.print("No");
}
// Driver code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 3, 0, 2, 1, 2 };
// Given start and end
int start = 2;
int K = 0;
int N = arr.length;
// Function call
solve(arr, N, start, K);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach
# DFS approach to check if traversal
# is possible or not
def check(arr, s_start, start, visited,
size, K):
# Base cases
if (start < 0 or start >= size or
visited[start]):
return False
# Check if start index value K
if (arr[start] == K and
start != s_start):
return True
# Mark as visited
visited[start] = True
# Check for both i + arr[i]
# and i - arr[i] recursively
return (check(arr, s_start,
start + arr[start],
visited, size, K) or
check(arr, s_start,
start - arr[start],
visited, size, K))
# Function to check if index with value
# K can be reached or not
def solve(arr, n, start, K):
# Initialize visited array
visited = [False] * n
# DFS Traversal
ans = check(arr, start, start,
visited, n, K)
# Print the result
if (ans):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == "__main__":
# Given array arr[]
arr = [ 3, 0, 2, 1, 2 ]
# Given start and end
start = 2
K = 0
N = len(arr)
# Function call
solve(arr, N, start, K)
# This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// DFS approach to check if traversal
// is possible or not
public static bool check(int[] arr, int s_start,
int start, bool[] visited,
int size, int K)
{
// Base cases
if (start < 0 || start >= size||
visited[start])
{
return false;
}
// Check if start index value K
if (arr[start] == K &&
start != s_start)
{
return true;
}
// Mark as visited
visited[start] = true;
// Check for both i + arr[i]
// and i - arr[i] recursively
return (check(arr, s_start,
start + arr[start],
visited, size, K) ||
check(arr, s_start,
start - arr[start],
visited, size, K));
}
// Function to check if index with value
// K can be reached or not
public static void solve(int[] arr, int n,
int start, int K)
{
// Initialize visited array
bool[] visited = new bool[n];
// DFS Traversal
bool ans = check(arr, start, start,
visited, n, K);
// Print the result
if (ans)
Console.Write("Yes");
else
Console.Write("No");
}
// Driver code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 3, 0, 2, 1, 2 };
// Given start and end
int start = 2;
int K = 0;
int N = arr.Length;
// Function call
solve(arr, N, start, K);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// DFS approach to check if traversal
// is possible or not
function check(arr, s_start,
start, visited,
size, K)
{
// Base cases
if (start < 0 || start >= size
|| visited[start]) {
return false;
}
// Check if start index value K
if (arr[start] == K
&& start != s_start) {
return true;
}
// Mark as visited
visited[start] = true;
// Check for both i + arr[i]
// and i - arr[i] recursively
return (check(arr, s_start,
start + arr[start],
visited, size, K)
|| check(arr, s_start,
start - arr[start],
visited, size, K));
}
// Function to check if index with value
// K can be reached or not
function solve(arr, n, start, K)
{
// Initialize visited array
var visited = Array(n).fill(false);
// DFS Traversal
var ans = check(arr, start, start,
visited, n, K);
// Print the result
if (ans)
document.write("Yes");
else
document.write("No");
}
// Driver Code
// Given array arr[]
var arr = [ 3, 0, 2, 1, 2 ];
// Given start and end
var start = 2;
var K = 0;
var N = arr.length;
// Function Call
solve(arr, N, start, K);
// This code is contributed by rrrtnx.
</script>
Producción
No
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Método 3: DFS (método eficiente): Seguiremos los pasos que se mencionan a continuación:
- Como la array contiene solo un número positivo, cada vez que use dfs multiplique ese número con -1, lo que confirma que hemos visitado ese elemento antes.
- Compruebe si el elemento de índice dado es igual a K o no.
- De lo contrario, llame a dfs aumentando start + arr[start] y disminuyendo start – arr[start] .
- En el caso base, verifique si el inicio está dentro del rango de longitud de la array y también verifique si se visitó antes o no.
Implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// DFS approach to check if traversal
// is possible or not
bool dfs(int arr[], int N, int start, int K)
{
// Base cases
if (start < 0 || start >= N || arr[start] < 0)
return false;
// Marking visited
arr[start] *= -1;
// Checking is that the element we needed or not
// otherwise making call for dfs again for different
// positions
return (abs(arr[start]) == K)
|| dfs(arr, N, start + arr[start], K)
|| dfs(arr, N, start - arr[start], K);
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 3, 0, 2, 1, 2 };
// Given start and end
int start = 2;
int K = 0;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
bool flag = dfs(arr, N, start, K);
if (flag)
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG {
// DFS approach to check if traversal
// is possible or not
public static boolean dfs(int[] arr, int N, int start,
int K)
{
// Base Cases
if (start < 0 || start >= N || arr[start] < 0)
return false;
// Marking visited
arr[start] *= -1;
// Checking is that the element we needed or not
// otherwise making call for dfs again for different
// positions
return (Math.abs(arr[start]) == K)
|| dfs(arr, N, start + arr[start], K)
|| dfs(arr, N, start - arr[start], K);
}
// Driver code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 3, 0, 2, 1, 2 };
// Given start and end
int start = 2;
int K = 0;
int N = arr.length;
// Function call
if (dfs(arr, N, start, K))
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# Python3 program for the above approach
# DFS approach to check if traversal
# is possible or not
def dfs(arr, N, start, K):
# Base Cases
if start < 0 or start >= N or arr[start] < 0:
return False
# Marking visited
arr[start] *= -1
# Checking is that the element we needed or not
# otherwise making call for dfs again for different positions
return abs(arr[start]) == K or dfs(arr, N, start + arr[start], K) or dfs(arr, N, start - arr[start], K)
# Given array arr[]
arr = [ 3, 0, 2, 1, 2 ]
# Given start and end
start = 2
K = 0
N = len(arr)
# Function call
if dfs(arr, N, start, K):
print("Yes")
else:
print("No")
# This code is contributed by divyesh072019.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// DFS approach to check if traversal
// is possible or not
static bool dfs(int[] arr, int N, int start, int K)
{
// Base Cases
if (start < 0 || start >= N || arr[start] < 0)
return false;
// Marking visited
arr[start] *= -1;
// Checking is that the element we needed or not
// otherwise making call for dfs again for different
// positions
return (Math.Abs(arr[start]) == K)
|| dfs(arr, N, start + arr[start], K)
|| dfs(arr, N, start - arr[start], K);
}
static void Main()
{
// Given array arr[]
int[] arr = { 3, 0, 2, 1, 2 };
// Given start and end
int start = 2;
int K = 0;
int N = arr.Length;
// Function call
if (dfs(arr, N, start, K))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by rameshtravel07.
Javascript
<script>
// Javascript program for the above approach
// DFS approach to check if traversal
// is possible or not
function dfs(arr, N, start, K)
{
// Base Cases
if (start < 0 || start >= N || arr[start] < 0)
return false;
// Marking visited
arr[start] *= -1;
// Checking is that the element we needed or not
// otherwise making call for dfs again for different
// positions
return (Math.abs(arr[start]) == K)
|| dfs(arr, N, start + arr[start], K)
|| dfs(arr, N, start - arr[start], K);
}
// Given array arr[]
let arr = [ 3, 0, 2, 1, 2 ];
// Given start and end
let start = 2;
let K = 0;
let N = arr.length;
// Function call
if (dfs(arr, N, start, K))
document.write("Yes");
else
document.write("No");
// This code is contributed by mukesh07.
</script>
Producción
No
Complejidad de tiempo : O(n)
Espacio auxiliar: O (n), (el espacio solo se usa para la recursividad)
Publicación traducida automáticamente
Artículo escrito por animesh_ghosh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA