Dados dos números enteros N y B , la tarea es imprimir el índice máximo que puede alcanzar un puntero, comenzando desde el índice 0 th en una array de números naturales (es decir, 0, 1, 2, 3, 4, 5…), digamos arr [] , en N pasos sin colocarse en el índice B en ningún punto.
En cada paso, el puntero puede moverse del índice actual a un índice de salto o puede permanecer en el índice actual.
Índice de salto = Índice actual + Número de paso
Ejemplos:
Entrada: N = 3, B = 2
Salida: 6
Explicación:
Paso 1:
Índice actual = 0
Número de paso = 1
Índice de salto = 0 + 1 = 1
Paso 2: Índice actual = 1
Número de paso = 2
Índice de salto = 1 + 2 = 3
Paso 3:
Índice actual = 3
Número de paso = 3
Salto Índice = 3 + 3 = 6
Por lo tanto, el índice máximo que se puede alcanzar es 6.Entrada: N = 3, B = 1
Salida: 5
Explicación:
Paso 1:
Índice actual = 0
Número de paso = 1
Índice de salto = 0 + 1 = 1 Pero este es un índice malo. Entonces el puntero permanece en el índice actual.
Paso 2:
Índice actual = 0
Número de paso = 2
Índice de salto = 0 + 2 = 2
Paso 3:
Índice actual = 2
Número de paso = 3
Índice de salto = 2 + 3 = 5
Por lo tanto, el índice máximo que se puede alcanzar es 5.
Enfoque eficiente: el enfoque ingenuo que se analiza en este artículo también se puede optimizar mediante la búsqueda binaria . Si el valor de maximumIndex – B existe en la suma de los últimos K números de los primeros N números naturales, el valor de maximumIndex no se puede reducir a menos de 0 sin el salto en el índice B. por lo tanto, disminuya el índice máximo y realice los pasos anteriores nuevamente. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable maximumIndexReached como 0 .
- Inicialice el vector Ans[] .
- Itere sobre el rango [1, N] usando la variable i y agregue el valor i a la variable maximumIndexReached e inserte el valor i en el vector Ans[] .
- Invierta el vector Ans[] .
- Itere sobre el rango [1, Ans.size()) usando la variable i y agregue el valor Ans[i – 1] a Ans[i] .
- Atraviese un bucle while hasta que maximumIndexReached sea mayor que 0 y realice las siguientes tareas:
- Inicialice una variable automática como el puntero cuyo valor es mayor o igual que maximumIndexReached – B en la array Ans[] .
- Si es igual a Ans.end() , salga del bucle .
- Si *es igual a maximumIndexReached – B entonces disminuye el valor de maximumIndexReached en 1 . De lo contrario, sal del bucle.
- Después de realizar los pasos anteriores, imprima el valor de maximumIndexReached como respuesta.
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
// reachable
int maxIndex(int N, int B)
{
// Store the answer
int maximumIndexReached = 0;
vector<int> Ans;
// Store the maximum index possible
// i.e, N*(N-1)
for (int i = 1; i <= N; i++) {
maximumIndexReached += i;
Ans.push_back(i);
}
reverse(Ans.begin(), Ans.end());
// Add bthe previous elements
for (int i = 1; i < (int)Ans.size(); i++) {
Ans[i] += Ans[i - 1];
}
// Run a loop
while (maximumIndexReached) {
// Binary Search
auto it
= lower_bound(Ans.begin(), Ans.end(),
maximumIndexReached - B);
if (it == Ans.end()) {
break;
}
if (*it == maximumIndexReached - B) {
maximumIndexReached--;
}
else {
break;
}
}
return maximumIndexReached;
}
// Driver Code
int main()
{
int N = 3, B = 2;
cout << maxIndex(N, B);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum index
// reachable
static int maxIndex(int N, int B)
{
// Store the answer
int maximumIndexReached = 0;
Vector<Integer> Ans = new Vector<>();
// Store the maximum index possible
// i.e, N*(N-1)
for (int i = 1; i <= N; i++) {
maximumIndexReached += i;
Ans.add(i+i-1);
}
// Run a loop
while (maximumIndexReached>0) {
// Binary Search
int it
= lower_bound(Ans, maximumIndexReached - B);
if (it == -1) {
break;
}
if (it == maximumIndexReached - B) {
maximumIndexReached--;
}
else {
break;
}
}
return maximumIndexReached;
}
public static int lower_bound(Vector<Integer> s, int val)
{
List<Integer> temp = new LinkedList<Integer>();
temp.addAll(s);
Collections.sort(temp);
Collections.reverse(temp);
if (temp.indexOf(val) + 1 == temp.size())
return -1;
else if(temp.get(temp.indexOf(val) +1)>val)
return -1;
else
return temp.get(temp.indexOf(val) +1);
}
// Driver Code
public static void main(String[] args)
{
int N = 3, B = 2;
System.out.print(maxIndex(N, B));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python 3 program for the above approach from bisect import bisect_left # Function to find the maximum index # reachable def maxIndex(N, B): # Store the answer maximumIndexReached = 0 Ans = [] # Store the maximum index possible # i.e, N*(N-1) for i in range(1, N + 1): maximumIndexReached += i Ans.append(i) Ans.reverse() # Add bthe previous elements for i in range(len(Ans)): Ans[i] += Ans[i - 1] # Run a loop while (maximumIndexReached): # Binary Search it = bisect_left(Ans, maximumIndexReached - B) if (it not in Ans): break if (it == maximumIndexReached - B): maximumIndexReached -= 1 else: break return maximumIndexReached # Driver Code if __name__ == "__main__": N = 3 B = 2 print(maxIndex(N, B)) # This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
function lowerBound(Ans, target)
{
const targetRange = [-1, -1]
const leftIdx = extremeInsertionIndex(Ans, target, true)
if (leftIdx === Ans.length || Ans[leftIdx] != target)
return targetRange
targetRange[0] = leftIdx
targetRange[1] = extremeInsertionIndex(Ans, target, false) - 1
return targetRange
function extremeInsertionIndex(Ans, target, left) {
let lo = 0,
hi = Ans.length
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2)
if (Ans[mid] > target || (left && target === Ans[mid]))
hi = mid
else
lo = mid + 1
}
return lo
}
}
// Function to find the maximum index
// reachable
function maxIndex(N, B)
{
// Store the answer
let maximumIndexReached = 0;
let Ans = [];
// Store the maximum index possible
// i.e, N*(N-1)
for (let i = 1; i <= N; i++) {
maximumIndexReached += i;
Ans.push(i);
}
Ans.reverse();
// Add bthe previous elements
for (let i = 1; i < Ans.length; i++) {
Ans[i] += Ans[i - 1];
}
// Run a loop
while (maximumIndexReached)
{
// Binary Search
let it
= lowerBound(Ans, maximumIndexReached - B);
if (it == -1) {
break;
}
if (it == maximumIndexReached - B) {
maximumIndexReached--;
}
else {
break;
}
}
return maximumIndexReached;
}
// Driver Code
let N = 3, B = 2;
document.write(maxIndex(N, B));
// This code is contributed by Potta Lokesh
</script>
6
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA