logo

Número K'th Boom

Prova-ho a GfG Practice ' title= #practiceLinkDiv { mostrar: cap !important; }

Els números boom són nombres formats només pels dígits 2 i 3. Donat un enter k (0 Exemples: 

Input : k = 2 Output: 3 Input : k = 3 Output: 22 Input : k = 100 Output: 322323 Input: k = 1000000 Output: 3332322223223222223
Recommended Practice Número de boom K Prova-ho!

La idea és molt senzilla com Genera nombres binaris . Aquí també fem servir el mateix enfocament  



utilitzem l'estructura de dades de la cua per resoldre aquest problema. Primera cua '2' i després '3', aquests dos són el primer i el segon nombre de boom respectivament. Ara establiu count=2 per cada cop que aparegui () davant de la cua i afegiu "2" al nombre aparegut i incrementeu count++ si (count==k) després imprimiu l'actual Número de boom en cas contrari, afegiu "3" al nombre emergent i incrementeu count++ si (count==k) i imprimiu el corrent Número de boom . Repetiu el procés fins a arribar a K'th Número de boom .

Aquest enfocament es pot veure com el BFS d'un arbre amb l'arrel com a cadena buida. El fill esquerre de cada node té 2 afegits i el fill dret 3. 

A continuació es mostra la implementació d'aquesta idea. 



C++
// C++ program to find K'th Boom number #include   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'
'
) // 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'
'
) // K'th Boom number break } } return } // Driver program to test above function let k = 1000000 boomNumber(k) // This code is contributed by shinjanpatra </script>

Sortida
3332322223223222223

Complexitat temporal: O(K)
Espai auxiliar: O(n)

Aquest article ha estat revisat per l'equip GeeksforGeeks.