Número de dígitos en el número n formado por cuatro dígitos dados

Encuentra el número de dígitos en el número n construido usando 6, 1, 4 y 9 como los únicos dígitos en orden ascendente.
Los primeros números construidos usando solo 6, 1, 4 y 9 como dígitos en orden ascendente serían: 1, 6, 4, 
9, 11, 14, 16, 19, 41, 44, 46, 49, 61, 64 , 66, 69, 91, 94, 96, 99, 111, 114, 116, 119 y así sucesivamente. 

Ejemplos: 

Input : 6
Output : 2
6th digit of the series is 14 which has 2 digits.

Input : 21
Output : 3
21st digit of the series is 111 which has 3 digits.

Enfoque simple: Este es un enfoque de fuerza bruta.
1. Inicialice un número a 1 y un contador a 0.
2. Compruebe si el número inicializado tiene solo 6, 1, 4 o 9 como dígitos.
3. Si solo tiene los dígitos mencionados, aumente el contador en 1. 
4. Aumente el número y repita los pasos anteriores hasta que el contador sea menor que n.
Nota: El valor de n podría ser grande y, por lo tanto, este enfoque no puede funcionar porque no es eficiente en el tiempo.

Enfoque eficiente: puede calcular la cantidad de números de k dígitos en O (1) tiempo y siempre serán potencia de 4, por ejemplo, la cantidad de números de 1 dígito en la serie sería 4, la cantidad de números de 2 dígitos en la serie sería 16 y así sucesivamente. 

1. Cuente todos los números de k dígitos subsiguientes y siga sumándolos a una suma.
2. Rompa el bucle cuando la suma sea mayor o igual que n.
3. Mantenga un contador para realizar un seguimiento del número de dígitos.
4. El valor del contador en la ruptura del bucle indicará la respuesta.

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

// C++ program to count number of digits
// in n-th number made of given four digits.
#include <bits/stdc++.h>
using namespace std;
 
// Efficient function to calculate number
// of digits in the nth number constructed
// by using 6, 1, 4 and 9 as digits in the
// ascending order.
int number_of_digits(int n)
{
    int i, res, sum = 0;
 
    // Number of digits increase after
    // every i-th number where i increases in
    // powers of 4.
    for (i = 4, res = 1;; i *= 4, res++) {
        sum += i;
        if (sum >= n)
            break;       
    }
    return res;
}
 
// Driver code
int main()
{
    int n = 21;
    cout << number_of_digits(n) << endl;
    return 0;
}
//Thic code is contributed by Mayank Tyagi

// Java program to count
// number of digits in
// n-th number made of
// given four digits.
import java.io.*;
 
class GFG {
 
    // Efficient function to
    // calculate number of digits
    // in the nth number constructed
    // by using 6, 1, 4 and 9 as
    // digits in the ascending order.
    static int number_of_digits(int n)
    {
        int i;
        int res;
        int sum = 0;
 
        // Number of digits increase
        // after every i-th number
        // where i increases in powers of 4.
        for (i = 4, res = 1;; i *= 4, res++) {
            sum += i;
            if (sum >= n)
                break;
        }
        return res;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 21;
        System.out.println(number_of_digits(n));
    }
}
 
// This code is contributed
// by akt_mit

# Python3 program to count number of
# digits in n-th number made of given
# four digits.
 
# Efficient function to calculate number
# of digits in the nth number constructed
# by using 6, 1, 4 and 9 as digits in the
# ascending order.
 
 
def number_of_digits(n):
 
    i = 4
    res = 1
    sum = 0
 
    # Number of digits increase after
    # every i-th number where i increases
    # in powers of 4.
    while(True):
        i *= 4
        res += 1
        sum += i
        if(sum >= n):
            break
    return res
 
 
# Driver Code
n = 21
print(number_of_digits(n))
 
# This code is contributed by mits

// C#  program to count
// number of digits in
// n-th number made of
// given four digits.
 
using System;
 
public class GFG {
 
    // Efficient function to
    // calculate number of digits
    // in the nth number constructed
    // by using 6, 1, 4 and 9 as
    // digits in the ascending order.
    static int number_of_digits(int n)
    {
        int i;
        int res;
        int sum = 0;
 
        // Number of digits increase
        // after every i-th number
        // where i increases in powers of 4.
        for (i = 4, res = 1;; i *= 4, res++) {
            sum += i;
            if (sum >= n)
                break;
        }
        return res;
    }
 
    // Driver Code
 
    static public void Main()
    {
 
        int n = 21;
        Console.WriteLine(number_of_digits(n));
    }
}

<?php
// PHP program to count number
// of digits in n-th number
// made of given four digits.
 
// Efficient function to
// calculate number of digits
// in the nth number constructed
// by using 6, 1, 4 and 9 as
// digits in the ascending order.
function number_of_digits($n)
{
    $i; $res; $sum = 0;
 
    // Number of digits increase
    // after every i-th number
    // where i increases in
    // powers of 4.
    for ($i = 4, $res = 1;;
         $i *= 4, $res++)
    {
        $sum += $i;
        if ($sum >= $n)
            break;
    }
    return $res;
}
 
// Driver Code
$n = 21;
echo number_of_digits($n),"\n";
     
// This code is contributed by ajit
?>

<script>
 
// Javascript program to count number of digits
// in n-th number made of given four digits.
 
// Efficient function to calculate number
// of digits in the nth number constructed
// by using 6, 1, 4 and 9 as digits in the
// ascending order.
function number_of_digits(n)
{
    let i, res, sum = 0;
 
    // Number of digits increase after
    // every i-th number where i increases in
    // powers of 4.
    for(i = 4, res = 1;; i *= 4, res++)
    {
        sum += i;
         
        if (sum >= n)
            break;   
    }
    return res;
}
 
// Driver code
let n = 21;
 
document.write(number_of_digits(n) + "<br>");
 
// This code is contributed by Manoj.
 
</script>

3

Complejidad de tiempo: O(logn), donde n representa el entero dado.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.

Nota: Dado que n podría ser realmente grande, hemos utilizado la biblioteca de impulso, para saber más sobre la biblioteca de impulso, lea este artículo: C++ avanzado con biblioteca de impulso