Dadas dos arrays A[] y B[] que consisten en N enteros donde A[i] representa la posición inicial del i -ésimo avión y B[i] es la velocidad a la que aterriza el avión, la tarea es imprimir el número del avión que se puede evitar que aterrice disparando un avión cada segundo.
Ejemplos:
Entrada: A[] = {1, 3, 5, 4, 8}, B[] = {1, 2, 2, 1, 2}
Salida: 4
Explicación:
- En el segundo 1, dispare el avión en el índice 0, las posiciones de los aviones ahora son A[] = {_, 1, 3, 3, 6}.
- En el segundo 2, dispare el avión en el índice 1, las posiciones de los aviones ahora son A[] = {_, _, 1, 2, 4}.
- En el segundo 3, dispare el avión en el índice 2, las posiciones de los aviones ahora son A[] = {_, _, _, 1, 2}.
- En el segundo 4, dispare el avión en el índice 4 o 5, las posiciones de los aviones ahora son A[] = {_, _, _, _, _}.
Por lo tanto, se puede evitar que aterricen un total de 4 aviones.
Entrada: A[] = {2, 8, 2, 3, 1}, B[] = {1, 4, 2, 2, 2}
Salida: 2
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Se puede observar que el conteo de aviones que se pueden detener es el conjunto de tiempos distintos que se necesitan para aterrizar para cada avión, ya que a la vez, solo se puede destruir un avión.
- El tiempo que tarda un avión en aterrizar es A[i] / B[i] y se puede calcular con la fórmula: Tiempo = Distancia / Velocidad
Siga los pasos a continuación para resolver el problema:
- Inicialice un Hash-Set , digamos S que almacena los tiempos necesarios para el aterrizaje del avión.
- Itere sobre un rango [0, N] usando la variable i y realice las siguientes tareas:
- Inicialice una variable, diga t como 1 si el valor de A[i]%B[i] es mayor que 0 . De lo contrario, actualice la variable t como 0 .
- Agregue el valor de A[i]/B[i] a la variable, digamos t .
- Agregue el valor de t en HashSet S .
- Después de realizar los pasos anteriores, devuelva el tamaño de HashSet como la respuesta resultante.
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 find maximum number
// of planes that can be stopped
// from landing
int maxPlanes(int A[], int B[], int N)
{
// Stores the times needed for
// landing for each plane
set<int> St;
// Iterate over the arrays
for (int i = 0; i < N; i++) {
// Stores the time needed for
// landing of current plane
int t = (A[i] % B[i] > 0) ? 1 : 0;
// Update the value of t
t += (A[i] / B[i]) + t;
// Append the t in set St
St.insert(t);
}
// Return the answer
return St.size();
}
// Driver Code
int main() {
int A[] = { 1, 3, 5, 4, 8 };
int B[] = { 1, 2, 2, 1, 2 };
int N = sizeof(A)/sizeof(A[0]);
cout << maxPlanes(A, B, N);
return 0;
}
// This code is contributed by Dharanendra L V.
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find maximum number
// of planes that can be stopped
// from landing
static int maxPlanes(int[] A, int[] B)
{
// Stores the times needed for
// landing for each plane
Set<Integer> St = new HashSet<>();
// Iterate over the arrays
for (int i = 0; i < A.length; i++) {
// Stores the time needed for
// landing of current plane
int t = (A[i] % B[i] > 0) ? 1 : 0;
// Update the value of t
t += (A[i] / B[i]) + t;
// Append the t in set St
St.add(t);
}
// Return the answer
return St.size();
}
// Driver Code
public static void main(String[] args)
{
int[] A = { 1, 3, 5, 4, 8 };
int[] B = { 1, 2, 2, 1, 2 };
System.out.println(
maxPlanes(A, B));
}
}
Python3
# Python program for the above approach # Function to find maximum number # of planes that can be stopped # from landing def maxPlanes(A, B, N): # Stores the times needed for # landing for each plane St = set() # Iterate over the arrays for i in range(N): # Stores the time needed for # landing of current plane t = 1 if (A[i] % B[i] > 0) else 0 # Update the value of t t += (A[i] // B[i]) + t # Append the t in set St St.add(t) # Return the answer return len(St) # Driver Code A = [ 1, 3, 5, 4, 8 ] B = [ 1, 2, 2, 1, 2 ] N = len(A) print(maxPlanes(A, B, N)) # This code is contributed by shivanisinghss2110
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find maximum number
// of planes that can be stopped
// from landing
static int maxPlanes(int[] A, int[] B)
{
// Stores the times needed for
// landing for each plane
HashSet<int> St = new HashSet<int>();
// Iterate over the arrays
for (int i = 0; i < A.Length; i++) {
// Stores the time needed for
// landing of current plane
int t = (A[i] % B[i] > 0) ? 1 : 0;
// Update the value of t
t += (A[i] / B[i]) + t;
// Append the t in set St
St.Add(t);
}
// Return the answer
return St.Count;
}
// Driver code
static public void Main (){
int[] A = { 1, 3, 5, 4, 8 };
int[] B = { 1, 2, 2, 1, 2 };
Console.WriteLine(
maxPlanes(A, B));
}
}
// This code is contributed by Potta Lokesh
Javascript
<script>
// Function to find maximum number
// of planes that can be stopped
// from landing
function maxPlanes(A, B)
{
// Stores the times needed for
// landing for each plane
let St = new Set();
// Iterate over the arrays
for (let i = 0; i < A.length; i++) {
// Stores the time needed for
// landing of current plane
let t = (A[i] % B[i] > 0) ? 1 : 0;
// Update the value of t
t += Math.floor(A[i] / B[i]) + t;
// Append the t in set St
St.add(t);
}
// Return the answer
return St.size;
}
// Driver Code
let A = [ 1, 3, 5, 4, 8 ];
let B = [ 1, 2, 2, 1, 2 ];
document.write(
maxPlanes(A, B));
// This code is contributed by sanjoy_62.
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)