Boom numbers are numbers consisting only of digits 2 and 3. Given an integer k (0<k<=10^7) , display the k-th Boom number.
Examples:
Input : k = 2 Output: 3 Input : k = 3 Output: 22 Input : k = 100 Output: 322323 Input: k = 1000000 Output: 3332322223223222223
The idea is very simple like Generate Binary Numbers . Here also we use same approach ,
we use queue data structure to solve this problem. First enqueue “2” then “3” these two are first and second boom number respectively. Now set count=2, for each time pop() front of queue and append “2” in popped number and increment count++ if (count==k) then print current Boom number else append “3” in popped number and increment count++ if (count==k) then print current Boom number. Repeat the process until we reach to K’th Boom number.
This approach can be seen as BFS of a tree with root as empty string. Left child of every node has a 2 appended and right child has 3 appended.
Below is the implementation of this 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 numbervoid 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 functionint 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 numberdef 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 functionk = 1000000boomNumber(k)# This code is contributed by shinjanpatra |
C#
// C# program to find K'th Boom numberusing System;using System.Collections; class GFG{// This function uses queue data structure// to K'th Boom numberstatic 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 numberfunction 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 functionlet k = 1000000boomNumber(k)// This code is contributed by shinjanpatra</script> |
Output
3332322223223222223
Time Complexity: O(K)
Auxiliary Space: O(n)
This article is reviewed by team neveropen.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
