Dado un número N, la tarea es imprimir la string de ‘A’ y ‘B’ correspondiente a ese número.
Si representamos todos los números como una string de ‘A’ y ‘B’ de la siguiente manera,
1 = A 2 = B 3 = AA 4 = AB 5 = BA 6 = BB 7 = AAA 8 = AAB 9 = ABA 10 = ABB ..... ..... 1000000 = BBBABAAAABAABAAAAAB
Ejemplos:
Input: N = 30 Output: BBBB Input: N = 55 Output: BBAAA Input: N = 100 Output: BAABAB
Acercarse:
- Esta representación está un poco relacionada con la representación binaria.
- Primero, tenemos que encontrar el número de caracteres necesarios para imprimir la string correspondiente al número dado. Esa es la longitud de la string resultante.
- Hay 2 números de longitud 1, 4 números de longitud 2, 8 números de longitud 3 y así sucesivamente…
- Por lo tanto, una string de longitud k de ‘A’ y ‘B’ puede representar números pow(2, k) desde (pow(2, k)-2)+1 hasta pow(2, k+1)-2, es decir, AA …A (k veces) a BB…B (k veces).
- Por lo tanto, para imprimir la string correspondiente, primero calcule la longitud de la string, sea k. Ahora calcula,
N = M - (pow(2, k)-2);
- Ahora ejecute el siguiente bucle para imprimir la string correspondiente.
while (k>0) { num = pow(2, k-1); if (num >= N) cout <<"A"; else{ cout <<"B"; N -= num; } k--; }
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
BBBB BBAAA BAABAB
Publicación traducida automáticamente
Artículo escrito por Vivek.Pandit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA