Encuentre la n-ésima string binaria en orden ordenado

Dado un entero positivo n , la tarea es encontrar la n ^-ésima string en la siguiente lista infinita de todas las strings posibles sobre dos símbolos a y b ordenados lexicográficamente (Diccionario). 

a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, … 
 

Ejemplos:  

Entrada: n = 6 
Salida: bb

Entrada: n = 11 
Salida: baa 

Un enfoque simple es generar todas las strings hasta n y luego determinar la n ^-ésima string. Sin embargo, el enfoque no es adecuado para valores grandes de n .

Un enfoque eficiente se basa en el hecho de que el número de strings de longitud k que se pueden generar usando 2 símbolos es 2 ^k . En base a esto, podemos calcular el índice relativo a partir del índice real (n) con respecto a la longitud de la string en la lista. La string en el ^índice n se puede determinar fácilmente usando la forma binaria del índice relativo a medida que se ordena la lista. La siguiente fórmula se utiliza para el cálculo, 

índice relativo = n + 1 – 2 ^{piso(log(n + 1))} 
 

Considere el siguiente ejemplo:  

Sea n = 11 y luego floor(log(n + 1)) = 3 . 
Esto sugiere que el índice n consta de una string de longitud 3 y una forma de inicio de strings de longitud 3 (2 ³ – 1) = 7.° índice y 7.° índice contiene la string “aaa”. 
Por lo tanto, índice relativo = 11 + 1 – 2 ³ = 4 . 
Este es el índice relativo a 7 . Ahora, la string en el índice n = 11 se puede obtener simplemente a partir de la interpretación binaria del índice relativo 4 . 
Aquí 0 significa a y 1 significa b. La siguiente tabla ilustra esto: 
 

Por lo tanto, la string presente en el índice 11 (índice relativo 4 ) es «baa»

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function to return the nth string in the required sequence
string obtain_str(ll n)
{
 
    // Length of the resultant string
    ll len = (int)log2(n + 1);
 
    // Relative index
    ll rel_ind = n + 1 - pow(2, len);
 
    ll i = 0;
    string str = "";
    for (i = 0; i < len; i++) {
 
        // Initial string of length len consists of
        // all a's since the list is sorted
        str += 'a';
    }
 
    i = 0;
 
    // Convert relative index to Binary form and set
    // 0 = a and 1 = b
    while (rel_ind > 0) {
        if (rel_ind % 2 == 1)
            str[i] = 'b';
        rel_ind /= 2;
        i++;
    }
 
    // Reverse and return the string
    reverse(str.begin(), str.end());
    return str;
}
 
// Driver function
int main()
{
    ll n = 11;
    cout << obtain_str(n);
 
    return 0;
}

// Java Implementation of the above approach
import java.io.*;
import java.util.*;
class Gfg {
 
    // Function to return the nth string in the required sequence
    static String obtain_str(int n)
    {
        // Length of the resultant string
        int len = (int)Math.floor((Math.log(n + 1) / Math.log(2)));
 
        // Relative Index
        int rel_ind = n + 1 - (int)Math.pow(2, len);
 
        int i = 0;
        StringBuilder str = new StringBuilder();
        for (i = 0; i < len; i++) {
 
            // Initial string of length len consists of
            // all a's since the list is sorted
            str.append('a');
        }
 
        i = 0;
 
        // Convert relative index to Binary form and set
        // 0 = a and 1 = b
        while (rel_ind > 0) {
            if (rel_ind % 2 == 1)
                str.setCharAt(i, 'b');
            rel_ind /= 2;
            i++;
        }
 
        // Reverse and return the string
        str = str.reverse();
        return str.toString();
    }
 
    // Driver function
    public static void main(String args[])
    {
        int n = 11;
        System.out.print(obtain_str(n));
    }
}

# Python3 implementation of the
# above approach
 
# from math lib import log2 function
from math import log2
 
# Function to return the nth string
# in the required sequence
def obtain_str(n) :
 
    # Length of the resultant string
    length = int(log2(n + 1))
 
    # Relative index
    rel_ind = n + 1 - pow(2, length)
 
    i = 0
    string = ""
     
    for i in range(length) :
 
        # Initial string of length len consists
        # of all a's since the list is sorted
        string += 'a'
 
    i = 0
     
    string_list = list(string)
     
    # Convert relative index to Binary
    # form and set 0 = a and 1 = b
    while (rel_ind > 0) :
        if (rel_ind % 2 == 1) :
            string_list[i] = 'b'
             
        rel_ind //= 2
        i += 1
     
    # Reverse and return the string
    string_list.reverse()
    string = "".join(string_list)
     
    return string
 
# Driver Code
if __name__ == "__main__" :
 
    n = 11
    print(obtain_str(n))
 
# This code is contributed by Ryuga

// C# Implementation of the above approach
using System;
using System.Text;
 
class GFG
{
 
    // Function to return the nth string
    // in the required sequence
    static String obtain_str(int n)
    {
        // Length of the resultant string
        int len = (int)Math.Floor((Math.Log(n + 1) /
                                    Math.Log(2)));
 
        // Relative Index
        int rel_ind = n + 1 - (int)Math.Pow(2, len);
 
        int i = 0;
        StringBuilder str = new StringBuilder();
        for (i = 0; i < len; i++)
        {
 
            // Initial string of length len consists of
            // all a's since the list is sorted
            str.Append('a');
        }
 
        i = 0;
 
        // Convert relative index to Binary form and set
        // 0 = a and 1 = b
        while (rel_ind > 0)
        {
            if (rel_ind % 2 == 1)
                str[i]='b';
            rel_ind /= 2;
            i++;
        }
 
        // Reverse and return the string
        return reverse(str.ToString());
    }
     
    static String reverse(String input)
    {
        char[] a = input.ToCharArray();
        int l, r = a.Length - 1;
        for (l = 0; l < r; l++, r--)
        {
            char temp = a[l];
            a[l] = a[r];
            a[r] = temp;
        }
        return String.Join("", a);
    }
     
    // Driver function
    public static void Main(String []args)
    {
        int n = 11;
        Console.Write(obtain_str(n));
    }
}
 
// This code is contributed by PrinciRaj1992

<?php
// PHP implementation of the above approach
 
// Function to return the nth string
// in the required sequence
function obtain_str($n)
{
 
    // Length of the resultant string
    $len = (int)(log($n + 1) / log(2));
 
    // Relative index
    $rel_ind = $n + 1 - pow(2, $len);
 
    $i = 0;
    $str = "";
    for ($i = 0; $i < $len; $i++)
    {
 
        // Initial string of length len
        // consists of all a's since the
        // list is sorted
        $str .= 'a';
    }
 
    $i = 0;
 
    // Convert relative index to Binary
    // form and set 0 = a and 1 = b
    while ($rel_ind > 0)
    {
        if ($rel_ind % 2 == 1)
            $str[$i] = 'b';
        $rel_ind = (int)($rel_ind / 2);
        $i++;
    }
 
    // Reverse and return the string
    return strrev($str);
}
 
// Driver Code
$n = 11;
echo obtain_str($n);
 
// This code is contributed
// by chandan_jnu
?>

<script>
 
// Javascript Implementation of the above approach
 
// Function to return the nth string
// in the required sequence
function obtain_str(n)
{
     
    // Length of the resultant string
    let len = Math.floor((Math.log(n + 1) /
                          Math.log(2)));
 
    // Relative Index
    let rel_ind = n + 1 - Math.pow(2, len);
 
    let i = 0;
    let str = [];
     
    for(i = 0; i < len; i++)
    {
         
        // Initial string of length len consists of
        // all a's since the list is sorted
        str.push('a');
    }
 
    i = 0;
 
    // Convert relative index to Binary
    // form and set 0 = a and 1 = b
    while (rel_ind > 0)
    {
        if (rel_ind % 2 == 1)
            str[i]='b';
             
        rel_ind = parseInt(rel_ind / 2, 10);
        i++;
    }
 
    // Reverse and return the string
    return reverse(str.join(""));
}
   
function reverse(input)
{
    let a = input.split('');
    let l, r = a.length - 1;
     
    for(l = 0; l < r; l++, r--)
    {
        let temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }
    return a.join("");
}
 
// Driver code
let n = 11;
 
document.write(obtain_str(n));
 
// This code is contributed by rameshtravel07
 
</script>

baa

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)