Los números de boom son números que consisten solo en los dígitos 2 y 3. Dado un número entero k (0<k<=10^7), muestra el k-ésimo número de Boom.
Ejemplos:
Input : k = 2 Output: 3 Input : k = 3 Output: 22 Input : k = 100 Output: 322323 Input: k = 1000000 Output: 3332322223223222223
La idea es muy simple como Generar Números Binarios . Aquí también usamos el mismo enfoque,
usamos la estructura de datos de la cola para resolver este problema. Primero ponga en cola «2» y luego «3», estos dos son el primer y segundo número de boom respectivamente. Ahora configure el conteo = 2, para cada vez que aparezca() al frente de la cola y agregue «2» en el número emergente e incremente el conteo ++ si (recuento == k) luego imprima el número de Boom actual ; de lo contrario, agregue «3» en el número emergente e incremente el conteo ++ si (count==k) luego imprime el número de Boom actual . Repite el proceso hasta llegar al número de K’th Boom .
Este enfoque puede verse como BFS de un árbol con la raíz como una string vacía. El hijo izquierdo de cada Node tiene 2 adjuntos y el hijo derecho tiene 3 adjuntos.
A continuación se muestra la implementación de esta idea.
C++
// C++ program to find K'th Boom number
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
// This function uses queue data structure to K'th
// Boom number
void boomNumber(ll k)
{
// Create an empty queue of strings
queue<string> q;
// Enqueue an empty string
q.push("");
// counter for K'th element
ll count = 0;
// This loop checks the value of count to
// become equal to K when value of count
// will be equals to k we will print the
// Boom number
while (count <= k)
{
// current Boom number
string s1 = q.front();
// pop front
q.pop();
// Store current Boom number before changing it
string s2 = s1;
// Append "2" to string s1 and enqueue it
q.push(s1.append("2"));
count++;
// check if count==k
if (count==k)
{
cout << s1 << endl; // K'th Boom number
break;
}
// Append "3" to string s2 and enqueue it.
// Note that s2 contains the previous front
q.push(s2.append("3"));
count++;
// check if count==k
if (count==k)
{
cout << s2 << endl; // K'th Boom number
break;
}
}
return ;
}
// Driver program to test above function
int main()
{
ll k = 1000000;
boomNumber(k);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG
{
// This function uses queue data structure to K'th
// Boom number
static void boomNumber(long k)
{
// Create an empty queue of strings
Queue<String> q = new LinkedList<String>();
// Enqueue an empty string
q.add("");
// counter for K'th element
long count = 0;
// This loop checks the value of count to
// become equal to K when value of count
// will be equals to k we will print the
// Boom number
while (count <= k)
{
// current Boom number
String s1 = q.poll();
// Store current Boom number before changing it
String s2 = s1;
// Append "2" to string s1 and enqueue it
q.add(s1+"2");
count++;
// check if count==k
if (count==k)
{
System.out.println(s1); // K'th Boom number
break;
}
// Append "3" to string s2 and enqueue it.
// Note that s2 contains the previous front
q.add(s2+"3");
count++;
// check if count==k
if (count==k)
{
System.out.println(s2); // K'th Boom number
break;
}
}
return ;
}
// Driver code
public static void main(String args[])
{
long k = 1000000;
boomNumber(k);
}
}
// This code is contributed by shinjanpatra
Python3
# Python3 program to find K'th Boom number
# This function uses queue data structure to K'th
# Boom number
def boomNumber(k):
# Create an empty queue of strings
q = []
# Enqueue an empty string
q.append("")
# counter for K'th element
count = 0
# This loop checks the value of count to
# become equal to K when value of count
# will be equals to k we will print the
# Boom number
while (count <= k):
# current Boom number
s1 = q[0]
# pop front
q = q[1:]
# Store current Boom number before changing it
s2 = s1
# Append "2" to string s1 and enqueue it
s1 += '2'
q.append(s1)
count = count + 1
# check if count==k
if (count==k):
print(s1) # K'th Boom number
break
# Append "3" to string s2 and enqueue it.
# Note that s2 contains the previous front
s2 += '3'
q.append(s2)
count = count + 1
# check if count==k
if (count==k):
print(s2) # K'th Boom number
break
return
# Driver program to test above function
k = 1000000
boomNumber(k)
# This code is contributed by shinjanpatra
C#
// C# program to find K'th Boom number
using System;
using System.Collections;
class GFG{
// This function uses queue data structure
// to K'th Boom number
static void boomNumber(long k)
{
// Create an empty queue of strings
Queue q = new Queue();
// Enqueue an empty string
q.Enqueue("");
// counter for K'th element
long count = 0;
// This loop checks the value of count to
// become equal to K when value of count
// will be equals to k we will print the
// Boom number
while (count <= k)
{
// current Boom number
string s1 = (string)q.Dequeue();
// Store current Boom number
// before changing it
string s2 = s1;
// Append "2" to string s1 and
// enqueue it
s1 += "2";
q.Enqueue(s1);
count++;
// Check if count==k
if (count == k)
{
// K'th Boom number
Console.Write(s1);
break;
}
// Append "3" to string s2 and enqueue it.
// Note that s2 contains the previous front
s2 += "3";
q.Enqueue(s2);
count++;
// Check if count==k
if (count == k)
{
// K'th Boom number
Console.Write(s2);
break;
}
}
return;
}
// Driver code
public static void Main(string []arg)
{
long k = 1000000;
boomNumber(k);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program to find K'th Boom number
// This function uses queue data structure to K'th
// Boom number
function boomNumber(k){
// Create an empty queue of strings
let q = []
// Enqueue an empty string
q.push("")
// counter for K'th element
let count = 0
// This loop checks the value of count to
// become equal to K when value of count
// will be equals to k we will print the
// Boom number
while (count <= k){
// current Boom number
let s1 = q.shift()
// Store current Boom number before changing it
let s2 = s1
// Append "2" to string s1 and enqueue it
s1 += '2'
q.push(s1)
count = count + 1
// check if count==k
if (count==k){
document.write(s1,"</br>") // K'th Boom number
break
}
// Append "3" to string s2 and enqueue it.
// Note that s2 contains the previous front
s2 += '3'
q.push(s2)
count = count + 1
// check if count==k
if (count==k){
document.write(s2,"</br>") // K'th Boom number
break
}
}
return
}
// Driver program to test above function
let k = 1000000
boomNumber(k)
// This code is contributed by shinjanpatra
</script>
Producción
3332322223223222223
Este artículo es una contribución de Shashank Mishra (Gullu) . Este artículo está revisado por el equipo GeeksforGeeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA