Dada una array arr[] de enteros, donde el i -ésimo entero representa la posición donde está presente una isla, y un entero k (1 ≤ k < N). Una persona está parada en la isla 0 y tiene que llegar a la última isla, saltando de una isla a otra en exactamente k saltos, la tarea es encontrar el mínimo de la longitud máxima de un salto que hará una persona en su viaje . Tenga en cuenta que la posición de todas las islas se dan en orden ascendente.
Ejemplos:
Entrada: arr[] = {2, 15, 36, 43}, k = 1
Salida: 41
Solo hay forma de llegar al final
2 -> 43
Entrada: arr[] = {2, 15, 36, 43}, k = 2
Salida: 28
Hay dos formas de llegar a la última isla
2 -> 15 -> 43
Aquí la distancia máxima entre dos islas consecutivas está entre 43 y 15, es decir 28.
2 -> 36 -> 43
Aquí la distancia máxima entre cualquiera de las dos islas consecutivas está entre 36 y 2, es decir, 34.
Por lo tanto, el mínimo de 28 y 34 es 28.
Enfoque: la idea es usar la búsqueda binaria y, para una distancia media , calcular si es posible llegar al final de la array en exactamente k saltos donde la distancia máxima entre dos islas elegidas para saltar es menor o igual que la distancia mid , luego verifique si existe alguna distancia menor que mid para la cual es posible llegar al final en exactamente k saltos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if it is possible
// to reach end of the array in exactly k jumps
bool isPossible(int arr[], int n, int dist, int k)
{
// Variable to store the number of
// steps required to reach the end
int req = 0;
int curr = 0;
int prev = 0;
for (int i = 0; i < n; i++) {
while (curr != n && arr[curr] - arr[prev] <= dist)
curr++;
req++;
if (curr == n)
break;
prev = curr - 1;
}
if (curr != n)
return false;
// If it is possible to reach the
// end in exactly k jumps
if (req <= k)
return true;
return false;
}
// Returns the minimum maximum distance required
// to reach the end of the array in exactly k jumps
int minDistance(int arr[], int n, int k)
{
int l = 0;
int h = arr[n - 1];
// Stores the answer
int ans = 0;
// Binary search to calculate the result
while (l <= h) {
int m = (l + h) / 2;
if (isPossible(arr, n, m, k)) {
ans = m;
h = m - 1;
}
else
l = m + 1;
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 2, 15, 36, 43 };
int n = sizeof(arr) / sizeof(int);
int k = 2;
cout << minDistance(arr, n, k);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function that returns true if it is possible
// to reach end of the array in exactly k jumps
static boolean isPossible(int arr[], int n, int dist, int k)
{
// Variable to store the number of
// steps required to reach the end
int req = 0;
int curr = 0;
int prev = 0;
for (int i = 0; i < n; i++)
{
while (curr != n && arr[curr] - arr[prev] <= dist)
{
curr++;
}
req++;
if (curr == n)
{
break;
}
prev = curr - 1;
}
if (curr != n)
{
return false;
}
// If it is possible to reach the
// end in exactly k jumps
if (req <= k)
{
return true;
}
return false;
}
// Returns the minimum maximum distance required
// to reach the end of the array in exactly k jumps
static int minDistance(int arr[], int n, int k)
{
int l = 0;
int h = arr[n - 1];
// Stores the answer
int ans = 0;
// Binary search to calculate the result
while (l <= h)
{
int m = (l + h) / 2;
if (isPossible(arr, n, m, k))
{
ans = m;
h = m - 1;
}
else
{
l = m + 1;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {2, 15, 36, 43};
int n = arr.length;
int k = 2;
System.out.println(minDistance(arr, n, k));
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach # Function that returns true if it is possible # to reach end of the array in exactly k jumps def isPossible(arr, n, dist, k) : # Variable to store the number of # steps required to reach the end req = 0 curr = 0 prev = 0 for i in range(0, n): while (curr != n and (arr[curr] - arr[prev]) <= dist): curr = curr + 1 req = req + 1 if (curr == n): break prev = curr - 1 if (curr != n): return False # If it is possible to reach the # end in exactly k jumps if (req <= k): return True return False # Returns the minimum maximum distance required # to reach the end of the array in exactly k jumps def minDistance(arr, n, k): l = 0 h = arr[n - 1] # Stores the answer ans = 0 # Binary search to calculate the result while (l <= h): m = (l + h) // 2; if (isPossible(arr, n, m, k)): ans = m h = m - 1 else: l = m + 1 return ans # Driver code arr = [ 2, 15, 36, 43 ] n = len(arr) k = 2 print(minDistance(arr, n, k)) # This code is contributed by ihritik
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function that returns true if it is possible
// to reach end of the array in exactly k jumps
static bool isPossible(int []arr, int n, int dist, int k)
{
// Variable to store the number of
// steps required to reach the end
int req = 0;
int curr = 0;
int prev = 0;
for (int i = 0; i < n; i++)
{
while (curr != n && arr[curr] - arr[prev] <= dist)
{
curr++;
}
req++;
if (curr == n)
{
break;
}
prev = curr - 1;
}
if (curr != n)
{
return false;
}
// If it is possible to reach the
// end in exactly k jumps
if (req <= k)
{
return true;
}
return false;
}
// Returns the minimum maximum distance required
// to reach the end of the array in exactly k jumps
static int minDistance(int []arr, int n, int k)
{
int l = 0;
int h = arr[n - 1];
// Stores the answer
int ans = 0;
// Binary search to calculate the result
while (l <= h)
{
int m = (l + h) / 2;
if (isPossible(arr, n, m, k))
{
ans = m;
h = m - 1;
}
else
{
l = m + 1;
}
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {2, 15, 36, 43};
int n = arr.Length;
int k = 2;
Console.WriteLine(minDistance(arr, n, k));
}
}
/* This code contributed by PrinciRaj1992 */
PHP
<?php
// Php implementation of the approach
// Function that returns true if it is possible
// to reach end of the array in exactly k jumps
function isPossible($arr, $n, $dist, $k)
{
// Variable to store the number of
// steps required to reach the end
$req = 0;
$curr = 0;
$prev = 0;
for ($i = 0; $i < $n; $i++)
{
while ($curr != $n && $arr[$curr] - $arr[$prev] <= $dist)
$curr++;
$req++;
if ($curr == $n)
break;
$prev = $curr - 1;
}
if ($curr != $n)
return false;
// If it is possible to reach the
// end in exactly k jumps
if ($req <= $k)
return true;
return false;
}
// Returns the minimum maximum distance required
// to reach the end of the array in exactly k jumps
function minDistance($arr, $n, $k)
{
$l = 0;
$h = $arr[$n - 1];
// Stores the answer
$ans = 0;
// Binary search to calculate the result
while ($l <= $h)
{
$m = floor(($l + $h) / 2);
if (isPossible($arr, $n, $m, $k))
{
$ans = $m;
$h = $m - 1;
}
else
$l = $m + 1;
}
return $ans;
}
// Driver code
$arr = array( 2, 15, 36, 43 );
$n = count($arr);
$k = 2;
echo minDistance($arr, $n, $k);
// This code is contributed by Ryuga
?>
Javascript
<script>
// Javascript implementation of the approach
// Function that returns true if it is possible
// to reach end of the array in exactly k jumps
function isPossible(arr, n, dist, k)
{
// Variable to store the number of
// steps required to reach the end
let req = 0;
let curr = 0;
let prev = 0;
for (let i = 0; i < n; i++)
{
while (curr != n && arr[curr] - arr[prev] <= dist)
{
curr++;
}
req++;
if (curr == n)
{
break;
}
prev = curr - 1;
}
if (curr != n)
{
return false;
}
// If it is possible to reach the
// end in exactly k jumps
if (req <= k)
{
return true;
}
return false;
}
// Returns the minimum maximum distance required
// to reach the end of the array in exactly k jumps
function minDistance(arr, n, k)
{
let l = 0;
let h = arr[n - 1];
// Stores the answer
let ans = 0;
// Binary search to calculate the result
while (l <= h)
{
let m = Math.floor((l + h) / 2);
if (isPossible(arr, n, m, k))
{
ans = m;
h = m - 1;
}
else
{
l = m + 1;
}
}
return ans;
}
// Driver Code
let arr = [2, 15, 36, 43];
let n = arr.length;
let k = 2;
document.write(minDistance(arr, n, k));
</script>
Producción:
28
Complejidad temporal: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA