logo

TechCodeview

第 K ブーム番号

GfG Practice で試してみる ' title= #practiceLinkDiv { 表示: なし !重要; }

ブーム番号は、数字 2 と 3 のみで構成される数字です。整数 k (0 例:  

Input : k = 2 Output: 3 Input : k = 3 Output: 22 Input : k = 100 Output: 322323 Input: k = 1000000 Output: 3332322223223222223
Recommended Practice 第 K ブーム番号 試してみてください!

アイデアは非常にシンプルです 2進数の生成 。ここでも同じアプローチを使用します  



この問題を解決するためにキュー データ構造を使用します。最初に「2」をキューに入れ、次に「3」をキューに入れます。これら 2 つはそれぞれ第 1 ブーム番号と第 2 ブーム番号です。ここで、キューの先頭に Pop() を実行するたびに count=2 を設定し、ポップされた数値に '2' を追加し、(count==k) の場合は count++ をインクリメントしてから、current を出力します。 ブーム番号 それ以外の場合は、ポップされた数値に「3」を追加し、count++ をインクリメントします (count==k) から、現在の値を出力します ブーム番号 。 K 番目に到達するまでプロセスを繰り返します ブーム番号 。

このアプローチは、ルートが空の文字列であるツリーの BFS として見ることができます。すべてのノードの左側の子には 2 が追加され、右側の子には 3 が追加されます。 

以下はこのアイデアの実装です。 



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>

出力 
3332322223223222223

時間計算量: O(K)
補助スペース: O(n)

この記事は GeeksforGeeks チームによってレビューされています。