Print a number as string of ‘A’ and ‘B’ in lexicographic order

0 0 8 minutes read

Given a number N, the task is to print the string of ‘A’ and ‘B’ corresponding to that number.
If we represent all numbers as a string of ‘A’ and ‘B’ as follows,

1 = A
2 = B
3 = AA
4 = AB
5 = BA
6 = BB
7 = AAA
8 = AAB
9 = ABA
10 = ABB
.....
.....
1000000 = BBBABAAAABAABAAAAAB

Examples:

Input: N = 30
Output: BBBB

Input: N = 55
Output: BBAAA

Input: N = 100
Output: BAABAB

Approach:

This representation is a little bit related to binary representation.
First, we have to find the number of characters required to print the string corresponding to the given number, That is the length of the resultant string.
There are 2 numbers of length 1, 4 numbers of length 2, 8 numbers of length 3 and so on…
Therefore, k length string of ‘A’ and ‘B’ can represent pow(2, k) numbers from (pow(2, k)-2)+1 to pow(2, k+1)-2, that is AA…A (k times) to BB…B (k times).
Therefore, for printing the corresponding string, first, calculate the length of the string, let it be k. Now calculate,
```
N = M - (pow(2, k)-2);
```

Now run the following loop to print the corresponding string.

while (k>0)
{
    num = pow(2, k-1);
    
    if (num >= N)
        cout <<"A";
    else{
        cout <<"B";
        N -= num;
    }
    k--;
}

Below is the implementation of the above approach:

C++

// C++ program to implement the above approach 
  
#include <cmath> 
#include <iostream> 
using namespace std; 
  
// Function to calculate number of characters 
// in corresponding string of 'A' and 'B' 
int no_of_characters(int M) 
{ 
  
    // Since the minimum number 
    // of characters will be 1 
    int k = 1; 
  
    // Calculating number of characters 
    while (true) { 
  
        // Since k length string can 
        // represent at most pow(2, k+1)-2 
        // that is if k = 4, it can 
        // represent at most pow(2, 4+1)-2 = 30 
        // so we have to calculate the 
        // length of the corresponding string 
        if (pow(2, k + 1) - 2 < M) 
            k++; 
        else
            break; 
    } 
  
    // return the length of 
    // the corresponding string 
    return k; 
} 
  
// Function to print corresponding 
// string of 'A' and 'B' 
void print_string(int M) 
{ 
    int k, num, N; 
  
    // Find length of string 
    k = no_of_characters(M); 
  
    // Since the first number that can be represented 
    // by k length string will be (pow(2, k)-2)+1 
    // and it will be AAA...A, k times, 
    // therefore, N will store that 
    // how much we have to print 
    N = M - (pow(2, k) - 2); 
  
    // At a particular time, 
    // we have to decide whether 
    // we have to print 'A' or 'B', 
    // this can be check by calculating 
    // the value of pow(2, k-1) 
    while (k > 0) { 
        num = pow(2, k - 1); 
  
        if (num >= N) 
            cout << "A"; 
        else { 
            cout << "B"; 
            N -= num; 
        } 
        k--; 
    } 
  
    // Print new line 
    cout << endl; 
} 
  
// Driver code 
int main() 
{ 
  
    int M; 
  
    M = 30; 
    print_string(M); 
  
    M = 55; 
    print_string(M); 
  
    M = 100; 
    print_string(M); 
  
    return 0; 
} 

Java

// Java implementation of the approach  
import java.util.*; 
  
class GFG 
{ 
      
// Function to calculate number of characters  
// in corresponding string of 'A' and 'B'  
static int no_of_characters(int M)  
{  
  
    // Since the minimum number  
    // of characters will be 1  
    int k = 1;  
  
    // Calculating number of characters  
    while (true) 
    {  
  
        // Since k length string can  
        // represent at most pow(2, k+1)-2  
        // that is if k = 4, it can  
        // represent at most pow(2, 4+1)-2 = 30  
        // so we have to calculate the  
        // length of the corresponding string  
        if ((int)Math.pow(2, k + 1) - 2 < M)  
            k++;  
        else
            break;  
    }  
  
    // return the length of  
    // the corresponding string  
    return k;  
}  
  
// Function to print corresponding  
// string of 'A' and 'B'  
static void print_string(int M)  
{  
    int k, num, N;  
  
    // Find length of string  
    k = no_of_characters(M);  
  
    // Since the first number that can be represented  
    // by k length string will be (pow(2, k)-2)+1  
    // and it will be AAA...A, k times,  
    // therefore, N will store that  
    // how much we have to print  
    N = M - ((int)Math.pow(2, k) - 2);  
  
    // At a particular time,  
    // we have to decide whether  
    // we have to print 'A' or 'B',  
    // this can be check by calculating  
    // the value of pow(2, k-1)  
    while (k > 0)  
    {  
        num = (int)Math.pow(2, k - 1);  
  
        if (num >= N)  
            System.out.print("A");  
        else 
        {  
            System.out.print( "B");  
            N -= num;  
        }  
        k--;  
    }  
  
    // Print new line  
    System.out.println();  
}  
  
// Driver code  
public static void main(String args[]) 
{  
  
    int M;  
  
    M = 30;  
    print_string(M);  
  
    M = 55;  
    print_string(M);  
  
    M = 100;  
    print_string(M);  
  
}  
} 
  
// This code is contributed by Arnab Kundu 

Python3

# Python 3 program to implement 
# the above approach 
from math import pow
  
# Function to calculate number of characters 
# in corresponding string of 'A' and 'B' 
def no_of_characters(M): 
      
    # Since the minimum number 
    # of characters will be 1 
    k = 1
  
    # Calculating number of characters 
    while (True): 
          
        # Since k length string can 
        # represent at most pow(2, k+1)-2 
        # that is if k = 4, it can 
        # represent at most pow(2, 4+1)-2 = 30 
        # so we have to calculate the 
        # length of the corresponding string 
        if (pow(2, k + 1) - 2 < M): 
            k += 1
        else: 
            break
  
    # return the length of 
    # the corresponding string 
    return k 
  
# Function to print corresponding 
# string of 'A' and 'B' 
def print_string(M): 
      
    # Find length of string 
    k = no_of_characters(M) 
  
    # Since the first number that can be  
    # represented by k length string will  
    # be (pow(2, k)-2)+1 and it will be  
    # AAA...A, k times, therefore, N will  
    # store that how much we have to print 
    N = M - (pow(2, k) - 2) 
  
    # At a particular time, 
    # we have to decide whether 
    # we have to print 'A' or 'B', 
    # this can be check by calculating 
    # the value of pow(2, k - 1) 
    while (k > 0): 
        num = pow(2, k - 1) 
  
        if (num >= N): 
            print("A", end = "") 
        else: 
            print("B", end = "") 
            N -= num 
        k -= 1
          
    print("\n", end = "") 
  
# Driver code 
if __name__ == '__main__': 
    M = 30; 
    print_string(M) 
  
    M = 55
    print_string(M) 
  
    M = 100
    print_string(M) 
      
# This code is contributed by 
# Surendra_Gangwar 

C#

// C# implementation of the approach  
using System; 
  
class GFG  
{  
      
    // Function to calculate number of characters  
    // in corresponding string of 'A' and 'B'  
    static int no_of_characters(int M)  
    {  
      
        // Since the minimum number  
        // of characters will be 1  
        int k = 1;  
      
        // Calculating number of characters  
        while (true)  
        {  
      
            // Since k length string can  
            // represent at most pow(2, k+1)-2  
            // that is if k = 4, it can  
            // represent at most pow(2, 4+1)-2 = 30  
            // so we have to calculate the  
            // length of the corresponding string  
            if ((int)Math.Pow(2, k + 1) - 2 < M)  
                k++;  
            else
                break;  
        }  
      
        // return the length of  
        // the corresponding string  
        return k;  
    }  
      
    // Function to print corresponding  
    // string of 'A' and 'B'  
    static void print_string(int M)  
    {  
        int k, num, N;  
      
        // Find length of string  
        k = no_of_characters(M);  
      
        // Since the first number that can be represented  
        // by k length string will be (pow(2, k)-2)+1  
        // and it will be AAA...A, k times,  
        // therefore, N will store that  
        // how much we have to print  
        N = M - ((int)Math.Pow(2, k) - 2);  
      
        // At a particular time,  
        // we have to decide whether  
        // we have to print 'A' or 'B',  
        // this can be check by calculating  
        // the value of pow(2, k-1)  
        while (k > 0)  
        {  
            num = (int)Math.Pow(2, k - 1);  
      
            if (num >= N)  
                Console.Write("A");  
            else
            {  
                Console.Write( "B");  
                N -= num;  
            }  
            k--;  
        }  
      
        // Print new line  
        Console.WriteLine();  
    }  
      
    // Driver code  
    public static void Main()  
    {  
      
        int M;  
      
        M = 30;  
        print_string(M);  
      
        M = 55;  
        print_string(M);  
      
        M = 100;  
        print_string(M);  
      
    }  
}  
  
// This code is contributed by Ryuga 

PHP

<?php 
// PHP program to implement  
// the above approach 
  
// Function to calculate number of characters 
// in corresponding string of 'A' and 'B' 
function no_of_characters($M) 
{ 
  
    // Since the minimum number 
    // of characters will be 1 
    $k = 1; 
  
    // Calculating number of characters 
    while (true) 
    { 
  
        // Since k length string can 
        // represent at most pow(2, k+1)-2 
        // that is if k = 4, it can 
        // represent at most pow(2, 4+1)-2 = 30 
        // so we have to calculate the 
        // length of the corresponding string 
        if (pow(2, $k + 1) - 2 < $M) 
            $k++; 
        else
            break; 
    } 
  
    // return the length of 
    // the corresponding string 
    return $k; 
} 
  
// Function to print corresponding 
// string of 'A' and 'B' 
function print_string($M) 
{ 
    $k; $num; $N; 
  
    // Find length of string 
    $k = no_of_characters($M); 
  
    // Since the first number that can be represented 
    // by k length string will be (pow(2, k)-2)+1 
    // and it will be AAA...A, k times, 
    // therefore, N will store that 
    // how much we have to print 
    $N = $M - (pow(2, $k) - 2); 
  
    // At a particular time, 
    // we have to decide whether 
    // we have to print 'A' or 'B', 
    // this can be check by calculating 
    // the value of pow(2, k-1) 
    while ($k > 0)  
    { 
        $num = pow(2, $k - 1); 
  
        if ($num >= $N) 
            echo "A"; 
        else { 
            echo "B"; 
            $N -= $num; 
        } 
        $k--; 
    } 
  
    // Print new line 
    echo "\n"; 
} 
  
// Driver code 
$M; 
  
$M = 30; 
print_string($M); 
  
$M = 55; 
print_string($M); 
  
$M = 100; 
print_string($M); 
  
// This code is contributed  
// by Akanksha Rai 
?> 

Javascript

<script> 
  
// JavaScript program to implement the above approach 
  
// Function to calculate number of characters 
// in corresponding string of 'A' and 'B' 
function no_of_characters( M){ 
    // Since the minimum number 
    // of characters will be 1 
    let k = 1; 
  
    // Calculating number of characters 
    while (true) { 
  
        // Since k length string can 
        // represent at most pow(2, k+1)-2 
        // that is if k = 4, it can 
        // represent at most pow(2, 4+1)-2 = 30 
        // so we have to calculate the 
        // length of the corresponding string 
        if (Math.pow(2, k + 1) - 2 < M) 
            k++; 
        else
            break; 
    } 
  
    // return the length of 
    // the corresponding string 
    return k; 
} 
  
// Function to print corresponding 
// string of 'A' and 'B' 
function print_string( M) 
{ 
    let k, num, N; 
  
    // Find length of string 
    k = no_of_characters(M); 
  
    // Since the first number that can be represented 
    // by k length string will be (pow(2, k)-2)+1 
    // and it will be AAA...A, k times, 
    // therefore, N will store that 
    // how much we have to print 
    N = M - (Math.pow(2, k) - 2); 
  
    // At a particular time, 
    // we have to decide whether 
    // we have to print 'A' or 'B', 
    // this can be check by calculating 
    // the value of pow(2, k-1) 
    while (k > 0) { 
        num = Math.pow(2, k - 1); 
  
        if (num >= N) 
            document.write( "A"); 
        else { 
            document.write( "B"); 
            N -= num; 
        } 
        k--; 
    } 
  
    // Print new line 
    document.write("<br>"); 
} 
  
// Driver code 
  
    let M; 
  
    M = 30; 
    print_string(M); 
  
    M = 55; 
    print_string(M); 
  
    M = 100; 
    print_string(M); 
      
</script>

Output:

BBBB
BBAAA
BAABAB

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!