K'inci Bom Numarası
GfG Practice'de deneyin 
#practiceLinkDiv { görüntü: yok !önemli; }
Çıkış
#practiceLinkDiv { görüntü: yok !önemli; } Bom numaraları yalnızca 2 ve 3 rakamlarından oluşan sayılardır. Bir k tam sayısı verildiğinde (0
Input : k = 2 Output: 3 Input : k = 3 Output: 22 Input : k = 100 Output: 322323 Input: k = 1000000 Output: 3332322223223222223Recommended Practice K'inci bom numarası Deneyin!
Fikir çok basit İkili Sayılar Oluşturun . Burada da aynı yaklaşımı kullanıyoruz
Bu sorunu çözmek için kuyruk veri yapısını kullanıyoruz. Önce '2'yi, ardından '3'ü sıralayın, bu ikisi sırasıyla birinci ve ikinci bom numarasıdır. Şimdi kuyruğun önündeki her pop() için count=2 değerini ayarlayın ve açılan sayıya '2' ekleyin ve count++ if (count==k) değerini artırın ve ardından akımı yazdırın Bom numarası Aksi halde açılan sayıya '3' ekleyin ve sayıyı artırın++ if (count==k) sonra geçerli olanı yazdırın Bom numarası . K'th'a ulaşana kadar işlemi tekrarlayın Bom numarası .
Bu yaklaşım, kökü boş dize olan bir ağacın BFS'si olarak görülebilir. Her düğümün sol çocuğuna 2 eklenir ve sağ çocuğuna 3 eklenir.
Aşağıda bu fikrin uygulanması yer almaktadır.
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>
Çıkış
3332322223223222223
Zaman Karmaşıklığı: O(K)
Yardımcı Alan: O(n)
Bu makale GeeksforGeeks ekibi tarafından incelenmiştir.
