Longitud máxima de la secuencia formada a partir del coste N

Dato norte monedas, el conjunto de números consta de {1, 2, 3, 4, ……..}. El costo de marcar un número en una secuencia es la cantidad de dígitos que contiene. (Por ejemplo el costo de elegir 2 es 1 y antes de 999 es 3), el trabajo es para Máximo número de elementos que puede contener un arreglo.

Cada elemento de {1, 2, 3, 4, ……..}. uso máximo 1 vez.

Ejemplos:

Aporte: norte = 11
Salida: 10
Explicación: En frente de norte = 11 -> seleccione 1 con costo 1, 2 con costo 1, 3 con costo 1, 4 con costo 1, 5 con costo 1, 6 con costo 1, 7 con costo 1, 8 con costo 1, 9 con costo 1, 10 con costo 2
costo total = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 = 11.

Aporte: norte = 189
Salida: 99

Enfoque ingenuo: La forma básica de resolver el problema es la siguiente:

Repetir i de 1 a infinito y calcular los costos de electricidad i como el costo de i es más que el número de monedas que es norte que yo – 1 será la respuesta.

Complejidad del tiempo: O(N * registroN)
cuarto auxiliar: O(1)

Enfoque eficiente: El enfoque anterior se puede optimizar en base a la siguiente idea:

Este problema se puede resolver usando Búsqueda binaria. Un número de dígitos con un costo dado es una función monótona de tipo TTTTTFFF F. La última vez que la función fue verdadera generará una respuesta para la longitud máxima de la secuencia.

Siga los pasos a continuación para resolver el problema:

• Si el costo requerido para las cifras de 1 Hasta que medio es menos que igual a norte Actualizando bajo de medio.
• De lo contrario elevado de medio – 1 ignorando la parte derecha del espacio de búsqueda.
• Antes de imprimir las respuestas después de la búsqueda binaria, verifique el número de dígitos de 1 Hasta que es alto Menos que o igual a norte si se imprime verdadero elevado
• Luego verifique el número de dígitos 1 Hasta que bajo es menor o igual que norte si se imprime verdadero bajo.
• Finalmente, si no se imprime nada desde arriba, imprima 0 ya que la longitud de la cadena es 0.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;

// Function to count total number
// of digits from numbers 1 to N
int totalDigits(int N)
{

    int cnt = 0LL;
    for (int i = 1; i <= N; i *= 10)
        cnt += (N - i + 1);

    return cnt;
}

// Function to find Maximum length of
// Sequence that can be formed from cost
// N
void findMaximumLength(int N)
{

    int low = 1, high = 1e9;

    while (high - low > 1) {
        int mid = low + (high - low) / 2;

        // Check if cost for number of digits
        // from 1 to N is less than equal to N
        if (totalDigits(mid) <= N) {

            // atleast mid will be the answer
            low = mid;
        }
        else {

            // igonre right search space
            high = mid - 1;
        }
    }

    // Check if high can be the answer
    if (totalDigits(high) <= N)
        cout << high << endl;

    // else low can be the answer
    else if (totalDigits(low) <= N)
        cout << low << endl;

    // else answer will be zero.
    else
        cout << 0 << endl;
}

// Driver Code
int main()
{

    int N = 11;

    // Function Call
    findMaximumLength(N);

    int N1 = 189;

    // Function call
    findMaximumLength(N1);

    return 0;
}

Complejidad del tiempo: O(registroN²) (el primer logN es para operaciones de logN de búsqueda binaria, el segundo logN es para encontrar el número de dígitos del 1 al N)
cuarto auxiliar: O(1)

Artículos relacionados: