Encuentre el n-ésimo elemento en una serie con solo 2 dígitos (4 y 7) permitidos | Conjunto 2 (método log(n))

Considere una serie de números compuesta solo por los dígitos 4 y 7. Los primeros números de la serie son 4, 7, 44, 47, 74, 77, 444, .. etc. Dado un número n, necesitamos encontrar n-th número en la serie.
Ejemplos: 
 

Input : n = 2
Output : 7

Input : n = 3
Output : 44

Input  : n = 5
Output : 74

Input  : n = 6
Output : 77

Hemos discutido una solución O (n) en la publicación a continuación. 
Encuentre el elemento n-th en una serie con solo 2 dígitos (4 y 7) permitidos
En esta publicación, se analiza una solución O (log n) que se basa en el siguiente patrón en números. Los números se pueden ver
 

                 ""
              /      \
            4         7
          /   \     /   \ 
        44    47   74    77
       / \   / \   / \  / \

La idea es llenar el número requerido desde el final. Sabemos que podemos observar que el último dígito es 4 si n es impar y el último dígito es 7 si n es par. Después de completar el último dígito, pasamos al Node principal en el árbol. Si n es impar, entonces el Node principal corresponde a (n-1/2. De lo contrario, el Node principal corresponde a (n-2)/2. 
 

// C++ program to find n-th number containing
// only 4 and 7.
#include<bits/stdc++.h>
using namespace std;
 
string findNthNo(int n)
{
    string res = "";
    while (n >= 1)
    {
        // If n is odd, append 4 and
        // move to parent
        if (n & 1)
        {
            res = res + "4";
            n = (n-1)/2;       
        }
 
        // If n is even, append 7 and
        // move to parent
        else
        {
            res = res + "7";
            n = (n-2)/2;     
        }
    }
 
   // Reverse res and return.
   reverse(res.begin(), res.end());
   return res;
}
 
// Driver code
int main()
{
    int n = 13;
    cout << findNthNo(n);
    return 0;
}

// java program to find n-th number
// containing only 4 and 7.
public class GFG {
     
    static String findNthNo(int n)
    {
        String res = "";
        while (n >= 1)
        {
             
            // If n is odd, append
            // 4 and move to parent
            if ((n & 1) == 1)
            {
                res = res + "4";
                n = (n - 1) / 2;    
            }
     
            // If n is even, append
            // 7 and move to parent
            else
            {
                res = res + "7";
                n = (n - 2) / 2;    
            }
        }
     
        // Reverse res and return.
        StringBuilder sb =
            new StringBuilder(res);
        sb.reverse();
        return new String(sb);
    }
     
    // Driver code
    public static void main(String args[])
    {
        int n = 13;
     
        System.out.print( findNthNo(n) );
    }
}
 
// This code is contributed by Sam007

# Python3 program to find
# n-th number containing
# only 4 and 7.
def reverse(s):
    if len(s) == 0:
        return s
    else:
        return reverse(s[1:]) + s[0]
         
def findNthNo(n):
    res = "";
    while (n >= 1):
         
        # If n is odd, append
        # 4 and move to parent
        if (n & 1):
            res = res + "4";
            n = (int)((n - 1) / 2);
             
            # If n is even, append7
            # and move to parent
        else:
            res = res + "7";
            n = (int)((n - 2) / 2);
             
    # Reverse res
    # and return.
    return reverse(res);
 
# Driver code
n = 13;
print(findNthNo(n));
 
# This code is contributed
# by mits

// C# program to find n-th number
// containing only 4 and 7.
using System;
class GFG {
 
static string findNthNo(int n)
{
    string res = "";
    while (n >= 1)
    {
         
        // If n is odd, append 4 and
        // move to parent
        if ((n & 1) == 1)
        {
            res = res + "4";
            n = (n - 1) / 2;    
        }
 
        // If n is even, append 7 and
        // move to parent
        else
        {
            res = res + "7";
            n = (n - 2) / 2;    
        }
    }
 
    // Reverse res and return.
    char[] arr = res.ToCharArray();
    Array.Reverse(arr);
    return new string(arr);
 
}
 
// Driver Code
public static void Main()
{
        int n = 13;
        Console.Write( findNthNo(n) );
}
}
 
// This code is contributed by Sam007

<?php
// PHP program to find
// n-th number containing
// only 4 and 7.
 
function findNthNo($n)
{
    $res = "";
    while ($n >= 1)
    {
        // If n is odd, append
        // 4 and move to parent
        if ($n & 1)
        {
            $res = $res . "4";
            $n = (int)(($n - 1) / 2);
        }
 
        // If n is even, append
        // 7 and move to parent
        else
        {
            $res = $res . "7";
            $n = (int)(($n - 2) / 2);
        }
    }
     
// Reverse res
// and return.
return strrev($res);
}
 
// Driver code
$n = 13;
echo findNthNo($n);
 
// This code is contributed
// by mits
?>

<script>
 
// javascript program to find n-th number
// containing only 4 and 7.
     
function findNthNo(n)
{
res = "";
while (n >= 1)
{
 
// If n is odd, append
// 4 and move to parent
if ((n & 1) == 1)
{
res = res + "4";
n = (n - 1) / 2;    
}
 
// If n is even, append
// 7 and move to parent
else
{
res = res + "7";
n = parseInt((n - 2) / 2);    
}
}
 
// Reverse res and return.
return res.split("").reverse().join("");
}
 
// Driver code
var n = 13;
 
document.write( findNthNo(n) );
 
// This code is contributed by 29AjayKumar
 
</script>

Producción:  

774

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.

En este código la complejidad total es O(log n). Porque while loop ejecuta el registro (n) veces.
Este artículo es una contribución de Devanshu Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.