Dados dos enteros N y B , la tarea es imprimir el índice máximo en una array que se puede alcanzar, comenzando desde el índice 0 , en N pasos sin ubicarse en el índice B en ningún punto, donde en cada i paso , El puntero puede mover i índices a la derecha.
Ejemplos:
Entrada: N = 4, B = 6
Salida: 9
Explicación: La siguiente secuencia de movimientos maximiza el índice que se puede alcanzar.
- Paso 1: Inicialmente, pos = 0. Permanecer en la misma posición.
- Paso 2: Mueve 2 índices a la derecha. Por lo tanto, posición actual = 0 + 2 = 2.
- Paso 3: Mueve 3 índices a la derecha. Por lo tanto, posición actual = 2 + 3 = 5.
- Paso 4: Mueve 4 índices a la derecha. Por lo tanto, posición actual = 5 + 4 = 9.
Entrada: N = 2, B = 2
Salida: 3
Enfoque ingenuo: consulte la publicación anterior para conocer el enfoque más simple para resolver el problema.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea más óptima para resolver el problema se basa en las siguientes observaciones:
Observación:
- Si se observa cuidadosamente, la respuesta es la secuencia de la suma aritmética de pasos o la de la suma aritmética de pasos: 1.
- Esto se debe a que se puede alcanzar el número más alto posible sin considerar B , sin esperar (lo que daría la suma aritmética).
- Pero si B es parte de esa secuencia, esperar en 0 en los primeros pasos asegura que la secuencia no se cruce con la secuencia obtenida sin esperar (ya que siempre está 1 detrás).
- Cualquier otra secuencia (es decir, esperar en cualquier otro punto una o más veces) siempre producirá un índice máximo alcanzable más pequeño.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos punteros i = 0 y j = 1.
- Inicialice una variable, digamos suma, para almacenar la suma de los primeros N números naturales , es decir , N * (N + 1) / 2.
- Inicialice una variable, diga cnt = 0 y otra variable, diga flag = false.
- Iterar hasta que cnt sea menor que N.
- Incrementa i con j .
- Incremento j .
- Incremento cnt .
- Si en cualquier iteración, i es igual a B , establezca flag = true y salga del ciclo.
- Si la bandera es falsa , imprima la suma . De lo contrario, imprima la suma – 1.
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 the maximum
// index the pointer can reach
int maximumIndex(int N, int B)
{
// Initialize two pointers
int i = 0, j = 1;
// Stores number of steps
int cnt = 0;
// Stores sum of first N
// natural numbers
int sum = N * (N + 1) / 2;
bool flag = false;
while (cnt < N) {
// Increment i with j
i += j;
// Increment j with 1
j++;
// Increment count
cnt++;
// If i points to B
if (i == B) {
// Break
flag = true;
break;
}
}
// Print the pointer index
if (!flag) {
cout << sum;
}
else
cout << sum - 1;
}
// Driver Code
int main()
{
// Given value of N & B
int N = 4, B = 6;
// Function call to find maximum
// index the pointer can reach
maximumIndex(N, B);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find the maximum
// index the pointer can reach
static void maximumIndex(int N, int B)
{
// Initialize two pointers
int i = 0, j = 1;
// Stores number of steps
int cnt = 0;
// Stores sum of first N
// natural numbers
int sum = N * (N + 1) / 2;
boolean flag = false;
while (cnt < N)
{
// Increment i with j
i += j;
// Increment j with 1
j++;
// Increment count
cnt++;
// If i points to B
if (i == B)
{
// Break
flag = true;
break;
}
}
// Print the pointer index
if (!flag == true)
{
System.out.print(sum);
}
else
{
System.out.print(sum - 1);
}
}
// Driver Code
public static void main (String[] args)
{
// Given value of N & B
int N = 4, B = 6;
// Function call to find maximum
// index the pointer can reach
maximumIndex(N, B);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to find the maximum # index the pointer can reach def maximumIndex(N, B): # Initialize two pointers i, j = 0, 1 # Stores number of steps cnt = 0 # Stores sum of first N # natural numbers sum = N * (N + 1) // 2 flag = False while (cnt < N): # Increment i with j i += j # Increment j with 1 j += 1 # Increment count cnt += 1 # If i points to B if (i == B): # Break flag = True break # Print the pointer index if (not flag): print (sum) else: print(sum - 1) # Driver Code if __name__ == '__main__': # Given value of N & B N, B = 4, 6 # Function call to find maximum # index the pointer can reach maximumIndex(N, B) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum
// index the pointer can reach
static void maximumIndex(int N, int B)
{
// Initialize two pointers
int i = 0, j = 1;
// Stores number of steps
int cnt = 0;
// Stores sum of first N
// natural numbers
int sum = N * (N + 1) / 2;
bool flag = false;
while (cnt < N)
{
// Increment i with j
i += j;
// Increment j with 1
j++;
// Increment count
cnt++;
// If i points to B
if (i == B)
{
// Break
flag = true;
break;
}
}
// Print the pointer index
if (!flag == true)
{
Console.Write(sum);
}
else
{
Console.Write(sum - 1);
}
}
// Driver Code
static public void Main ()
{
// Given value of N & B
int N = 4, B = 6;
// Function call to find maximum
// index the pointer can reach
maximumIndex(N, B);
}
}
// This code is contributed by avijitmondal1998
Javascript
<script>
// JavaScript program for the above approach
// Function to find the maximum
// index the pointer can reach
function maximumIndex(N, B)
{
// Initialize two pointers
let i = 0, j = 1;
// Stores number of steps
let cnt = 0;
// Stores sum of first N
// natural numbers
let sum = Math.floor(N * (N + 1) / 2);
let flag = false;
while (cnt < N) {
// Increment i with j
i += j;
// Increment j with 1
j++;
// Increment count
cnt++;
// If i points to B
if (i == B) {
// Break
flag = true;
break;
}
}
// Print the pointer index
if (!flag) {
document.write(sum);
}
else
document.write(sum - 1);
}
// Driver Code
// Given value of N & B
let N = 4, B = 6;
// Function call to find maximum
// index the pointer can reach
maximumIndex(N, B);
// This code is contributed by Surbhi Tyagi.
</script>
Producción
9
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Otro enfoque eficiente:
En el enfoque anterior, hemos establecido que el valor mínimo nunca puede ser menor que la (suma total de N número natural) – 1.
En este enfoque, intentaremos encontrar si B puede ocurrir en cualquiera de los pasos de una manera más óptima.
- La idea es usar la fórmula de la ecuación cuadrática para recuperar si existe un número x válido para el cual (x)(x+1)/2 = B .
- Como B ya está dada, podemos reescribir la ecuación como x 2 + x – 2B = 0 .
- Usando la fórmula cuadrática, podemos identificar si x es un número entero válido que satisface esta condición.
- Si encontramos una x válida, podemos devolver (N)(N+1)/2 – 1 . De lo contrario, podemos devolver directamente (N)(N+1)/2 .
A continuación se muestra la implementación del enfoque discutido:
C++
#include <iostream>
#include <math.h>
using namespace std;
bool isNaturalSum(int B){
float x=(-1+sqrt(1+8*B))/2;
//check for valid integer value of x
if(ceil(x)==floor(x))
return true;
else
return false;
}
int maximumIndex(int N, int B){
//Maximum Reachable value with N steps
long long int max_sum = ((N)*(N+1))/2;
//Determine if B lies in the sum of x natural numbers.
bool is_B_reachable = isNaturalSum(B);
//If B is reachable, don't include the first step else return the max_sum
if(is_B_reachable){
return max_sum - 1;
}
else{
return max_sum;
}
}
int main()
{
// Given value of N & B
int N = 3, B = 6;
// Function call to find maximum
// index the pointer can reach
cout<<maximumIndex(N, B)<<endl;
return 0;
}
Producción
5
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA