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> |
BBBB BBAAA BAABAB
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!