Conteo de operaciones de decremento requeridas para obtener K en N pasos

Dados dos números enteros N y K , que indican el número de operaciones permitidas y el número que debe obtenerse después de realizar N operaciones, respectivamente. Considere un valor S , inicialmente 0 , la tarea es convertir S en K realizando las siguientes operaciones N veces de cualquier manera:

1. Resta 1 de S .
2. Agregue P + 1 a S , donde P es el número agregado previamente ( inicialmente 0 ).

Si no es posible convertir S a K , imprima -1 . De lo contrario, imprima el número de operaciones de disminución que se requieren realizar.
Nota: S debe ser positivo después de cada operación realizada.

Ejemplos:

Entrada: N = 5, K = 4
Salida: 2
Explicación: 
El orden de las N operaciones realizadas: 
Paso 1: Sumar 1 a S convierte S = 1 
Paso 2: Sumar 2 a S convierte S = 3 
Paso 3: Restar 1 de S convierte S = 2 
Paso 4: Sumar 3 a S convierte S = 5 
Paso 5: Restar 1 de S convierte S = 4. 
Dado que S es igual a K después de N(= 5) operaciones, la respuesta es 2 como 2 operaciones decrecientes se realizan.

Entrada: N = 10, K = 3
Salida: -1

Enfoque ingenuo: la idea más simple es iterar un ciclo sobre el rango [1, N] y verificar las siguientes condiciones:

 

y yo + K = norte . 

Si existe algún valor de i del rango [1, N] que satisfaga las condiciones anteriores, imprima el valor de i . De lo contrario, imprima «-1» . 
Complejidad de Tiempo: O(N), donde N es el número máximo de pasos permitidos.
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la búsqueda binaria . A continuación se muestran los pasos:

1. Inicializa dos variables que comienzan como 0 y terminan como N .
2. Encuentre el índice medio de las dos variables anteriores tomando el promedio de inicio y fin .
3. Compruebe si podemos tener un número medio de pasos de Tipo 1 . En caso afirmativo, imprima la mitad y detenga la iteración.
4. De lo contrario, actualice el inicio o el final de acuerdo con los resultados que obtengamos al marcar mid y repita desde el paso 2.
5. Si no existe ningún medio que satisfaga la condición dada, imprima «-1» .

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 check whether m number
// of steps of type 1 are valid or not
int isValid(int n, int m, int k)
{
 
    // If m and n are the count of operations
    // of type 1 and type 2 respectively,
    // then n - m operations are performed
    int step2 = n - m;
 
    // Find the value of S after step 2
    int cnt = (step2 * (step2 + 1)) / 2;
 
    // If m steps of type 1 is valid
    if (cnt - m == k)
        return 0;
 
    if (cnt - m > k)
        return 1;
 
    return -1;
}
 
// Function to find the number of
// operations of type 1 required
void countOfOperations(int n, int k)
{
    int start = 0, end = n;
    bool ok = 1;
 
    // Iterate over the range
    while (start <= end) {
 
        // Find the value of mid
        int mid = (start + end) / 2;
 
        // Check if m steps of type 1
        // are valid or not
        int temp = isValid(n, mid, k);
 
        // If mid is the valid
        // number of steps
        if (temp == 0) {
            ok = 0;
            cout << mid;
            break;
        }
 
        else if (temp == 1) {
            start = mid + 1;
        }
 
        else {
            end = mid - 1;
        }
    }
 
    // If no valid number
    // of steps exist
    if (ok)
        cout << "-1";
}
 
// Driver Code
int main()
{
    // Given and N, K
    int N = 5, K = 4;
 
    // Function Call
    countOfOperations(N, K);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to check whether m number
// of steps of type 1 are valid or not
static int isValid(int n, int m, int k)
{
 
    // If m and n are the count of operations
    // of type 1 and type 2 respectively,
    // then n - m operations are performed
    int step2 = n - m;
 
    // Find the value of S after step 2
    int cnt = (step2 * (step2 + 1)) / 2;
 
    // If m steps of type 1 is valid
    if (cnt - m == k)
    return 0;
 
    if (cnt - m > k)
        return 1;
 
    return -1;
}
 
// Function to find the number of
// operations of type 1 required
static void countOfOperations(int n, int k)
{
    int start = 0, end = n;
    boolean ok = true;
 
    // Iterate over the range
    while (start <= end)
    {
         
        // Find the value of mid
        int mid = (start + end) / 2;
 
        // Check if m steps of type 1
        // are valid or not
        int temp = isValid(n, mid, k);
 
        // If mid is the valid
        // number of steps
        if (temp == 0)
        {
            ok = false;
            System.out.print(mid);
            break;
        }
 
        else if (temp == 1)
        {
            start = mid + 1;
        }
        else
        {
            end = mid - 1;
        }
    }
 
    // If no valid number
    // of steps exist
    if (ok)
        System.out.print("-1");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given and N, K
    int N = 5, K = 4;
 
    // Function call
    countOfOperations(N, K);
}
}
 
// This code is contributed by gauravrajput1

# Python3 program for the above approach
 
# Function to check whether m number
# of steps of type 1 are valid or not
def isValid(n, m, k):
 
    # If m and n are the count of operations
    # of type 1 and type 2 respectively,
    # then n - m operations are performed
    step2 = n - m
 
    # Find the value of S after step 2
    cnt = (step2 * (step2 + 1)) // 2
 
    # If m steps of type 1 is valid
    if (cnt - m == k):
        return 0
 
    if (cnt - m > k):
        return 1
 
    return -1
 
# Function to find the number of
# operations of type 1 required
def countOfOperations(n, k):
 
    start = 0
    end = n
    ok = 1
 
    # Iterate over the range
    while(start <= end):
 
        # Find the value of mid
        mid = (start + end) // 2
 
        # Check if m steps of type 1
        # are valid or not
        temp = isValid(n, mid, k)
 
        # If mid is the valid
        # number of steps
        if (temp == 0):
            ok = 0
            print(mid)
            break
 
        elif (temp == 1):
            start = mid + 1
        else:
            end = mid - 1
 
    # If no valid number
    # of steps exist
    if (ok):
        print("-1")
 
# Driver Code
 
# Given and N, K
N = 5
K = 4
 
# Function call
countOfOperations(N, K)
 
# This code is contributed by Shivam Singh

// C# program for
// the above approach
using System;
class GFG{
 
// Function to check
// whether m number of steps
// of type 1 are valid or not
static int isValid(int n,
                   int m, int k)
{
  // If m and n are the
  // count of operations
  // of type 1 and type 2
  // respectively, then n - m
  // operations are performed
  int step2 = n - m;
 
  // Find the value of S
  // after step 2
  int cnt = (step2 *
            (step2 + 1)) / 2;
 
  // If m steps of
  // type 1 is valid
  if (cnt - m == k)
    return 0;
 
  if (cnt - m > k)
    return 1;
 
  return -1;
}
 
// Function to find the
// number of operations
// of type 1 required 
static void countOfOperations(int n,
                              int k)
{
  int start = 0, end = n;
  bool ok = true;
 
  // Iterate over the range
  while (start <= end)
  {
    // Find the value of mid
    int mid = (start + end) / 2;
 
    // Check if m steps of type 1
    // are valid or not
    int temp = isValid(n, mid, k);
 
    // If mid is the valid
    // number of steps
    if (temp == 0)
    {
      ok = false;
      Console.Write(mid);
      break;
    }
 
    else if (temp == 1)
    {
      start = mid + 1;
    }
    else
    {
      end = mid - 1;
    }
  }
 
  // If no valid number
  // of steps exist
  if (ok)
    Console.Write("-1");
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given and N, K
  int N = 5, K = 4;
 
  // Function call
  countOfOperations(N, K);
}
}
 
// This code is contributed by Amit Katiyar

<script>
// Javascript program for the above approach
 
// Function to check whether m number
// of steps of type 1 are valid or not
function isValid(n, m, k)
{
 
    // If m and n are the count of operations
    // of type 1 and type 2 respectively,
    // then n - m operations are performed
    var step2 = n - m;
 
    // Find the value of S after step 2
    var cnt = parseInt((step2 * (step2 + 1)) / 2);
 
    // If m steps of type 1 is valid
    if (cnt - m == k)
        return 0;
 
    if (cnt - m > k)
        return 1;
 
    return -1;
}
 
// Function to find the number of
// operations of type 1 required
function countOfOperations(n, k)
{
    var start = 0, end = n;
    var ok = 1;
 
    // Iterate over the range
    while (start <= end) {
 
        // Find the value of mid
        var mid = parseInt((start + end) / 2);
 
        // Check if m steps of type 1
        // are valid or not
        var temp = isValid(n, mid, k);
 
        // If mid is the valid
        // number of steps
        if (temp == 0) {
            ok = 0;
            document.write( mid);
            break;
        }
 
        else if (temp == 1) {
            start = mid + 1;
        }
 
        else {
            end = mid - 1;
        }
    }
 
    // If no valid number
    // of steps exist
    if (ok)
        document.write( "-1");
}
 
// Driver Code
// Given and N, K
var N = 5, K = 4;
// Function Call
countOfOperations(N, K);
 
</script>

2

Complejidad de tiempo: O(log ₂ N), donde N son los pasos dados
Complejidad de espacio: O(1)