Dada una array arr[] de N enteros positivos y un número S , la tarea es llegar al final de la array desde el índice S. Solo podemos pasar del índice actual i al índice (i + arr[i]) o (i – arr[i]) . Si hay una manera de llegar al final de la array, imprima «Sí» , de lo contrario, imprima «No» .
Ejemplos:
Entrada: arr[] = {4, 1, 3, 2, 5}, S = 1
Salida: Sí
Explicación:
posición inicial: arr[S] = arr[1] = 1.
Saltos para llegar al final: 1 -> 4 -> 5
Por lo tanto, se ha llegado al final.Entrada: arr[] = {2, 1, 4, 5}, S = 2
Salida: No
Explicación:
posición inicial: arr[S] = arr[2] = 2.
Posibles saltos para llegar al final: 4 -> ( índice 7) o 4 -> (índice -2)
Dado que ambos están fuera de los límites, por lo tanto, no se puede alcanzar el final.
Enfoque 1: este problema se puede resolver utilizando Breadth First Search . A continuación se muestran los pasos:
- 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 último índice de la array, 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 llega al final de la array 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;
// Function to check if we can reach to
// the end of the arr[] with possible moves
void solve(int arr[], int n, int start)
{
// Queue to perform BFS
queue<int> q;
// Initially all nodes(index)
// are not visited.
bool visited[n] = { false };
// Initially the end of
// the array is not reached
bool reached = false;
// Push start index in queue
q.push(start);
// Until queue becomes empty
while (!q.empty()) {
// Get the top element
int temp = q.front();
// Delete popped element
q.pop();
// If the index is already
// visited. No need to
// traverse it again.
if (visited[temp] == true)
continue;
// Mark temp as visited
// if not
visited[temp] = true;
if (temp == n - 1) {
// If reached at the end
// of the array then break
reached = true;
break;
}
// If temp + arr[temp] and
// temp - arr[temp] are in
// the index of array
if (temp + arr[temp] < n) {
q.push(temp + arr[temp]);
}
if (temp - arr[temp] >= 0) {
q.push(temp - arr[temp]);
}
}
// If reaches the end of the array,
// Print "Yes"
if (reached == true) {
cout << "Yes";
}
// Else print "No"
else {
cout << "No";
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 4, 1, 3, 2, 5 };
// Starting index
int S = 1;
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
solve(arr, N, S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if we can reach to
// the end of the arr[] with possible moves
static void solve(int arr[], int n, int start)
{
// Queue to perform BFS
Queue<Integer> q = new LinkedList<>();
// Initially all nodes(index)
// are not visited.
boolean []visited = new boolean[n];
// Initially the end of
// the array is not reached
boolean reached = false;
// Push start index in queue
q.add(start);
// Until queue becomes empty
while (!q.isEmpty())
{
// Get the top element
int temp = q.peek();
// Delete popped element
q.remove();
// If the index is already
// visited. No need to
// traverse it again.
if (visited[temp] == true)
continue;
// Mark temp as visited
// if not
visited[temp] = true;
if (temp == n - 1)
{
// If reached at the end
// of the array then break
reached = true;
break;
}
// If temp + arr[temp] and
// temp - arr[temp] are in
// the index of array
if (temp + arr[temp] < n)
{
q.add(temp + arr[temp]);
}
if (temp - arr[temp] >= 0)
{
q.add(temp - arr[temp]);
}
}
// If reaches the end of the array,
// Print "Yes"
if (reached == true)
{
System.out.print("Yes");
}
// Else print "No"
else
{
System.out.print("No");
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 4, 1, 3, 2, 5 };
// Starting index
int S = 1;
int N = arr.length;
// Function call
solve(arr, N, S);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach
from queue import Queue
# Function to check if we can reach to
# the end of the arr[] with possible moves
def solve(arr, n, start):
# Queue to perform BFS
q = Queue()
# Initially all nodes(index)
# are not visited.
visited = [False] * n
# Initially the end of
# the array is not reached
reached = False
# Push start index in queue
q.put(start);
# Until queue becomes empty
while (not q.empty()):
# Get the top element
temp = q.get()
# If the index is already
# visited. No need to
# traverse it again.
if (visited[temp] == True):
continue
# Mark temp as visited, if not
visited[temp] = True
if (temp == n - 1):
# If reached at the end
# of the array then break
reached = True
break
# If temp + arr[temp] and
# temp - arr[temp] are in
# the index of array
if (temp + arr[temp] < n):
q.put(temp + arr[temp])
if (temp - arr[temp] >= 0):
q.put(temp - arr[temp])
# If reaches the end of the array,
# Print "Yes"
if (reached == True):
print("Yes")
# Else print "No"
else:
print("No")
# Driver code
if __name__ == '__main__':
# Given array arr[]
arr = [ 4, 1, 3, 2, 5 ]
# starting index
S = 1
N = len(arr)
# Function call
solve(arr, N, S)
# This code is contributed by himanshu77
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if we can reach to
// the end of the []arr with possible moves
static void solve(int []arr, int n,
int start)
{
// Queue to perform BFS
Queue<int> q = new Queue<int>();
// Initially all nodes(index)
// are not visited.
bool []visited = new bool[n];
// Initially the end of
// the array is not reached
bool reached = false;
// Push start index in queue
q.Enqueue(start);
// Until queue becomes empty
while (q.Count != 0)
{
// Get the top element
int temp = q.Peek();
// Delete popped element
q.Dequeue();
// If the index is already
// visited. No need to
// traverse it again.
if (visited[temp] == true)
continue;
// Mark temp as visited
// if not
visited[temp] = true;
if (temp == n - 1)
{
// If reached at the end
// of the array then break
reached = true;
break;
}
// If temp + arr[temp] and
// temp - arr[temp] are in
// the index of array
if (temp + arr[temp] < n)
{
q.Enqueue(temp + arr[temp]);
}
if (temp - arr[temp] >= 0)
{
q.Enqueue(temp - arr[temp]);
}
}
// If reaches the end of the array,
// Print "Yes"
if (reached == true)
{
Console.Write("Yes");
}
// Else print "No"
else
{
Console.Write("No");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 4, 1, 3, 2, 5 };
// Starting index
int S = 1;
int N = arr.Length;
// Function call
solve(arr, N, S);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript program for the above approach
// Function to check if we can reach to
// the end of the arr[] with possible moves
function solve(arr, n, start)
{
// Queue to perform BFS
let q = [];
// Initially all nodes(index)
// are not visited.
let visited = new Array(n);
visited.fill(false);
// Initially the end of
// the array is not reached
let reached = false;
// Push start index in queue
q.push(start);
// Until queue becomes empty
while (q.length > 0)
{
// Get the top element
let temp = q[0];
// Delete popped element
q.shift();
// If the index is already
// visited. No need to
// traverse it again.
if (visited[temp] == true)
continue;
// Mark temp as visited
// if not
visited[temp] = true;
if (temp == n - 1)
{
// If reached at the end
// of the array then break
reached = true;
break;
}
// If temp + arr[temp] and
// temp - arr[temp] are in
// the index of array
if (temp + arr[temp] < n)
{
q.push(temp + arr[temp]);
}
if (temp - arr[temp] >= 0)
{
q.push(temp - arr[temp]);
}
}
// If reaches the end of the array,
// Print "Yes"
if (reached == true)
{
document.write("Yes");
}
// Else print "No"
else
{
document.write("No");
}
}
// Driver code
// Given array arr[]
let arr = [ 4, 1, 3, 2, 5 ];
// Starting index
let S = 1;
let N = arr.length;
// Function Call
solve(arr, N, S);
// This code is contributed by divyeshrabadiya07
</script>
Producción:
Yes
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Enfoque 2:
- Otro enfoque para lo mismo puede ser mediante el uso de la recursividad.
- Usa la recursividad para saltar a la posición i + arr[i] e i – arr[i] de la array y comprueba si hemos llegado al final o no.
- La ventaja de usar el enfoque recursivo es que simplifica mucho el código. A continuación se muestra la implementación.
C++
// C++ program for the above approach
#include <iostream>
using namespace std;
bool check_the_end(int arr[], int n, int i)
{
// If we have reached out of bounds
// of the array then return False
if (i < 0 or i >= n)
return false;
// If we have reached the end then return True
if (i == n - 1)
return true;
// Either of the condition return true solved the
// problem
return check_the_end(arr, n, i - arr[i])
or check_the_end(arr, n, i + arr[i]);
}
// Driver Code
int main()
{
int arr[] = { 4, 1, 3, 2, 5 };
int S = 1;
int n = sizeof(arr) / sizeof(arr[0]);
bool result = check_the_end(arr, n, S);
cout << result;
}
// This Code is Contributed by Harshit Srivastava
Java
// Java program for the above approach
import java.io.*;
class GFG {
static boolean check_the_end(int arr[], int n, int i)
{
// If we have reached out of bounds
// of the array then return False
if (i < 0 || i >= n)
return false;
// If we have reached the end then return True
if (i == n - 1)
return true;
// Either of the condition return true solved the
// problem
return check_the_end(arr, n, i - arr[i])
|| check_the_end(arr, n, i + arr[i]);
}
// Driver Code
public static void main (String[] args) {
int arr[] = { 4, 1, 3, 2, 5 };
int S = 1;
int n = arr.length;
boolean result = check_the_end(arr, n, S);
System.out.println(result);
}
}
// This Code is Contributed by Shubhamsingh10
Python3
# Python program for the above approach def check_the_end(arr, i): # If we have reached out of bounds # of the array then return False if i < 0 or i >= len(arr): return False # If we have reached the end then return True if i == len(arr) - 1: return True # Either of the condition return true solved the problem return check_the_end(arr, i - arr[i]) or check_the_end(arr, i + arr[i]) # Driver Code arr = [4, 1, 3, 2, 5] S = 1 result = check_the_end(arr, S) print(result)
C#
// C# program for the above approach
using System;
public class GFG{
static bool check_the_end(int[] arr, int n, int i)
{
// If we have reached out of bounds
// of the array then return False
if (i < 0 || i >= n)
return false;
// If we have reached the end then return True
if (i == n - 1)
return true;
// Either of the condition return true solved the
// problem
return check_the_end(arr, n, i - arr[i])
|| check_the_end(arr, n, i + arr[i]);
}
// Driver Code
static public void Main (){
int[] arr = { 4, 1, 3, 2, 5 };
int S = 1;
int n = arr.Length;
bool result = check_the_end(arr, n, S);
Console.WriteLine(result);
}
}
// This Code is Contributed by Shubhamsingh10
Javascript
<script>
// JavaScript program for the above approach
function check_the_end(arr, n, i)
{
// If we have reached out of bounds
// of the array then return False
if (i < 0 || i >= n)
return false;
// If we have reached the end then return True
if (i == n - 1)
return true;
// Either of the condition return true solved the
// problem
return check_the_end(arr, n, i - arr[i])
|| check_the_end(arr, n, i + arr[i]);
}
// Driver Code
var arr = [4, 1, 3, 2, 5];
var S = 1
var n = arr.length;
var result = check_the_end(arr,n, S);
document.write(result)
// This code is contributed by Shivani
</script>
Producción:
True
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)