Número de un rango dado que requiere la K-ésima cantidad más pequeña de pasos para reducirse a 1

Dados tres enteros positivos L , R y K , la tarea es encontrar el número del rango [L, R] que requiere que el número de pasos más pequeño del K se ^reduzca a 1 realizando las siguientes operaciones:

• Si X es par , reduce X a X/2 .
• De lo contrario, establece X = (3*X + 1) .

Ejemplos:

Entrada: L = 7, R = 10, K = 4
Salida: 9
Explicación: 
El recuento de pasos para todos los números del rango [7, 10] es el siguiente:

• El número de pasos necesarios para 7 es 16. {7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 > 1}
• Del mismo modo, el número de pasos necesarios para 8 es 3.
• Del mismo modo, el número de pasos necesarios para 9 es 19.
• Del mismo modo, el número de pasos necesarios para 10 es 6.

Por lo tanto, el número de pasos necesarios para todos los valores del rango dado, ordenados en orden ascendente, son {3, 6, 16, 19} para los valores {8, 10, 7, 9} respectivamente. Por lo tanto, se requiere el K ^-ésimo número de pasos más pequeño para el número 9.

Entrada: L = 7, R = 10, K = 2
Salida: 10

Planteamiento: La idea es hacer funciones separadas para calcular el número de pasos para cada número del rango e imprimir el K ^-ésimo más pequeño de los valores obtenidos. Siga los pasos a continuación para resolver el problema:

• Defina una función power_value() para calcular la cantidad de pasos necesarios para un número:
  • Condición base: si el número es 1 , devuelve 0 .
  • Si el número es par , llama a la función power_value() con el valor número/2 .
  • De lo contrario, llame a la función power_value() con el número de valor * 3 + 1 .
• Ahora, para encontrar el K ^-ésimo número de pasos más pequeño , realice los siguientes pasos:
  • Inicializa un vector de pares , digamos ans .
  • Recorra la array en el rango [L, R] y calcule el valor de potencia del número actual i , e inserte un par de pasos e i en el vector de pares ans .
  • Ordene el vector en orden ascendente de la cuenta de pasos de ese número.
• Después de completar los pasos anteriores, imprima el K ^-ésimo número de pasos más pequeño desde el inicio, es decir, ans[K – 1].segundo como resultado.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
vector<ll> v(1000000, -1);
 
// Function to count the number of
// steps required to reduce val to
// 1 by the given operations
ll power_value(ll val)
{
    // Base Case
    if (val == 1)
        return 0;
 
    // If val is even, divide by 2
    if (val % 2 == 0) {
        v[val] = power_value(val / 2) + 1;
        return v[val];
    }
 
    // Otherwise, multiply it
    // by 3 and increment by 1
    else {
        ll temp = val * 3;
        temp++;
        v[val] = power_value(temp) + 1;
        return v[val];
    }
}
 
// Function to find Kth smallest
// count of steps required for
// numbers from the range [L, R]
ll getKthNumber(int l, int r, int k)
{
    // Stores numbers and their
    // respective count of steps
    vector<pair<ll, ll> > ans;
 
    // Count the number of steps for
    // all numbers from the range [L, R]
    for (ll i = l; i <= r; i++) {
        if (v[i] == -1)
            power_value(i);
    }
 
    ll j = 0;
 
    // Insert in the vector
    for (ll i = l; i <= r; i++) {
        ans.push_back(make_pair(v[i], i));
        j++;
    }
 
    // Sort the vector in ascending
    // order w.r.t. to  power value
    sort(ans.begin(), ans.end());
 
    // Print the K-th smallest number
    cout << ans[k - 1].second;
}
 
// Driver Code
int main()
{
    int L = 7, R = 10, K = 4;
    getKthNumber(L, R, K);
 
    return 0;
}

# Python3 program for the above approach
 
v = [-1]*(1000000)
 
# Function to count the number of
# steps required to reduce val to
# 1 by the given operations
def power_value(val):
   
    # Base Case
    if (val == 1):
        return 0
 
    # If val is even, divide by 2
    if (val % 2 == 0):
        v[val] = power_value(val // 2) + 1
        return v[val]
 
    # Otherwise, multiply it
    # by 3 and increment by 1
    else:
        temp = val * 3
        temp+=1
        v[val] = power_value(temp) + 1
        return v[val]
 
# Function to find Kth smallest
# count of steps required for
# numbers from the range [L, R]
def getKthNumber(l, r, k):
   
    # Stores numbers and their
    # respective count of steps
    ans = []
 
    # Count the number of steps for
    # anumbers from the range [L, R]
    for i in range(l, r + 1):
        if (v[i] == -1):
            power_value(i)
 
    j = 0
 
    # Insert in the vector
    for i in range(l, r + 1):
        ans.append([v[i], i])
        j += 1
 
    # Sort the vector in ascending
    # order w.r.t. to  power value
    ans = sorted(ans)
 
    # Print the K-th smallest number
    print (ans[k - 1][1])
 
# Driver Code
if __name__ == '__main__':
    L,R,K = 7, 10, 4
    getKthNumber(L, R, K)
 
    # This code is contributed by mohit kumar 29.

9

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)