NUMÉRO K'TH BOOM

Essayez-le sur GfG Practice ' title=

#practiceLinkDiv { display : aucun !important; }

Les nombres de flèche sont des nombres composés uniquement de chiffres 2 et 3. Étant donné un entier 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 Kème numéro de flèche Essayez-le !

L'idée est très simple comme Générer des nombres binaires . Ici aussi, nous utilisons la même approche

nous utilisons la structure de données de file d'attente pour résoudre ce problème. Mettez d'abord en file d'attente « 2 », puis « 3 », ces deux numéros étant respectivement le premier et le deuxième numéro de boom. Maintenant, définissez count=2 pour chaque fois que pop() devant la file d'attente et ajoutez '2' dans le numéro affiché et incrémentez count++ if (count==k), puis imprimez le courant Numéro de flèche sinon, ajoutez '3' dans le numéro affiché et incrémentez count++ si (count==k) puis imprimez le courant Numéro de flèche . Répétez le processus jusqu'à ce que nous atteignions K'th Numéro de flèche .

sauver de

Cette approche peut être considérée comme le BFS d’un arbre dont la racine est une chaîne vide. L'enfant gauche de chaque nœud a un 2 ajouté et l'enfant droit a 3 ajoutés.

Vous trouverez ci-dessous la mise en œuvre de cette idée.

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# 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>

Sortir

3332322223223222223

Complexité temporelle : O(K)
Espace auxiliaire : O(n)

formes normales

Cet article est révisé par l'équipe GeeksforGeeks.

TechCodeview