Índice máximo que un puntero puede alcanzar en N pasos evitando un índice B dado

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 ingenuo: el enfoque más simple para resolver el problema es calcular el índice máximo considerando dos posibilidades para cada Índice actual , ya sea para mover el puntero por Número de paso o permaneciendo en el Índice actual , y generar todas las combinaciones posibles. Finalmente, imprima el índice máximo obtenido. 

Complejidad de Tiempo: O(N ³ )
Espacio Auxiliar: O(1)

Enfoque eficiente:
calcule el índice máximo que se puede alcanzar dentro de los pasos dados. Si se puede alcanzar el índice 0 desde el índice máximo evitando el índice incorrecto, imprima el resultado ^. De lo contrario, repita el procedimiento disminuyendo el índice máximo en 1.
A continuación se muestran los pasos:

1. Calcula el índice máximo que se puede alcanzar en N pasos calculando la suma de los primeros N números naturales.
2. Asigne el valor del índice máximo calculado al Índice actual .
3. Siga disminuyendo el Índice actual por Número de paso y Número de paso en 1 hasta que uno de ellos se vuelva negativo.
4. Después de cada decremento, verifique si el Índice actual es igual a B o no. Si se determina que es cierto, revierte los cambios realizados en el índice actual .
5. Si el índice actual llega a 0 con éxito, imprima el valor actual del índice máximo como respuesta.
6. De lo contrario, disminuya el valor del índice máximo en 1 y repita desde el paso 2 .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum
// index the pointer can reach
void maximumIndex(int N, int B)
{
    int max_index = 0;
 
    // Calculate maximum possible
    // index that can be reached
    for (int i = 1; i <= N; i++) {
 
        max_index += i;
    }
 
    int current_index = max_index, step = N;
 
    while (1) {
 
        // Check if current index and step
        // both are greater than 0 or not
        while (current_index > 0 && N > 0) {
 
            // Decrement current_index by step
            current_index -= N;
 
            // Check if current index is
            // equal to B or not
            if (current_index == B) {
 
                // Restore to previous index
                current_index += N;
            }
 
            // Decrement step by one
            N--;
        }
 
        // If it reaches the 0th index
        if (current_index <= 0) {
 
            // Print result
            cout << max_index << endl;
            break;
        }
 
        // If max index fails to
        // reach the 0th index
        else {
 
            N = step;
 
            // Store max_index - 1 in current index
            current_index = max_index - 1;
 
            // Decrement max index
            max_index--;
 
            // If current index is equal to B
            if (current_index == B) {
 
                current_index = max_index - 1;
 
                    // Decrement current index
                    max_index--;
            }
        }
    }
}
 
// Driver Code
int main()
{
    int N = 3, B = 2;
    maximumIndex(N, B);
    return 0;
}

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to find the maximum
// index the pointer can reach
static void maximumIndex(int N,
                        int B)
{
int max_index = 0;
 
// Calculate maximum possible
// index that can be reached
for (int i = 1; i <= N; i++)
{
    max_index += i;
}
 
int current_index = max_index,
                    step = N;
 
while (true)
{
    // Check if current index
    // and step both are greater
    // than 0 or not
    while (current_index > 0 &&
        N > 0)
    {
    // Decrement current_index
    // by step
    current_index -= N;
 
    // Check if current index
    // is equal to B or not
    if (current_index == B)
    {
        // Restore to previous
        // index
        current_index += N;
    }
 
    // Decrement step by one
    N--;
    }
 
    // If it reaches the 0th index
    if (current_index <= 0)
    {
    // Print result
    System.out.print(max_index + "\n");
    break;
    }
 
    // If max index fails to
    // reach the 0th index
    else
    {
    N = step;
 
    // Store max_index - 1 in
    // current index
    current_index = max_index - 1;
 
    // Decrement max index
    max_index--;
 
    // If current index is
    // equal to B
    if (current_index == B)
    {
        current_index = max_index - 1;
 
        // Decrement current index
        max_index--;
    }
    }
}
}
 
// Driver Code
public static void main(String[] args)
{
int N = 3, B = 2;
maximumIndex(N, B);
}
}
 
// This code is contributed by gauravrajput1

# Python3 program for the above approach
 
# Function to find the maximum
# index the pointer can reach
def maximumIndex(N, B):
     
    max_index = 0
 
    # Calculate maximum possible
    # index that can be reached
    for i in range(1, N + 1):
        max_index += i
 
    current_index = max_index
    step = N
 
    while (1):
 
        # Check if current index and step
        # both are greater than 0 or not
        while (current_index > 0 and N > 0):
 
            # Decrement current_index by step
            current_index -= N
 
            # Check if current index is
            # equal to B or not
            if (current_index == B):
 
                # Restore to previous index
                current_index += N
 
            # Decrement step by one
            N -= 1
 
        # If it reaches the 0th index
        if (current_index <= 0):
             
            # Print result
            print(max_index)
            break
 
        # If max index fails to
        # reach the 0th index
        else:
            N = step
 
            # Store max_index - 1 in current index
            current_index = max_index - 1
 
            # Decrement max index
            max_index -= 1
 
            # If current index is equal to B
            if (current_index == B):
                current_index = max_index - 1
 
                # Decrement current index
                max_index -= 1
 
# Driver Code
if __name__ == '__main__':
     
    N = 3
    B = 2
     
    maximumIndex(N, B)
 
# This code is contributed by mohit kumar 29

// 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)
{
  int max_index = 0;
  
  // Calculate maximum possible
  // index that can be reached
  for(int i = 1; i <= N; i++)
  {
    max_index += i;
  }
  
  int current_index = max_index,
                      step = N;
  
  while (true)
  {
       
    // Check if current index
    // and step both are greater
    // than 0 or not
    while (current_index > 0 &&
                       N > 0)
    {
       
      // Decrement current_index
      // by step
      current_index -= N;
  
      // Check if current index
      // is equal to B or not
      if (current_index == B)
      {
           
        // Restore to previous
        // index
        current_index += N;
      }
  
      // Decrement step by one
      N--;
    }
  
    // If it reaches the 0th index
    if (current_index <= 0)
    {
         
      // Print result
      Console.Write(max_index + " ");
      break;
    }
  
    // If max index fails to
    // reach the 0th index
    else
    {
      N = step;
  
      // Store max_index - 1 in
      // current index
      current_index = max_index - 1;
  
      // Decrement max index
      max_index--;
  
      // If current index is
      // equal to B
      if (current_index == B)
      {
           
        current_index = max_index - 1;
  
        // Decrement current index
        max_index--;
      }
    }
  }
}
 
// Driver code
public static void Main (String[] args)
{
  int N = 3, B = 2;
   
  maximumIndex(N, B);
}
}
 
// This code is contributed by offbeat

<script>
 
// Javascript program for the above approach
 
// Function to find the maximum
// index the pointer can reach
function maximumIndex( N, B)
{
    var max_index = 0;
 
    // Calculate maximum possible
    // index that can be reached
    for (var i = 1; i <= N; i++) {
 
        max_index += i;
    }
 
    var current_index = max_index, step = N;
 
    while (1) {
 
        // Check if current index and step
        // both are greater than 0 or not
        while (current_index > 0 && N > 0) {
 
            // Decrement current_index by step
            current_index -= N;
 
            // Check if current index is
            // equal to B or not
            if (current_index == B) {
 
                // Restore to previous index
                current_index += N;
            }
 
            // Decrement step by one
            N--;
        }
 
        // If it reaches the 0th index
        if (current_index <= 0) {
 
            // Print result
            document.write(max_index + "<br>");;
            break;
        }
 
        // If max index fails to
        // reach the 0th index
        else {
 
            N = step;
 
            // Store max_index - 1 in current index
            current_index = max_index - 1;
 
            // Decrement max index
            max_index--;
 
            // If current index is equal to B
            if (current_index == B) {
 
                current_index = max_index - 1;
 
                    // Decrement current index
                    max_index--;
            }
        }
    }
}
 
// Driver Code
var N = 3, B = 2;
maximumIndex(N, B);
 
// This code is contributed by rrrtnx.
</script>

6

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)