K'th Bomnummer
Prøv det på GfG Practice 
#practiceLinkDiv { display: ingen !important; }
Produktion
#practiceLinkDiv { display: ingen !important; } Bomtal er tal, der kun består af cifrene 2 og 3. Givet et heltal k (0
Input : k = 2 Output: 3 Input : k = 3 Output: 22 Input : k = 100 Output: 322323 Input: k = 1000000 Output: 3332322223223222223Recommended Practice Kth bomnummer Prøv det!
Ideen er meget simpel Generer binære tal . Også her bruger vi samme tilgang
vi bruger kødatastruktur til at løse dette problem. Først kø '2' derefter '3' disse to er henholdsvis første og anden bomnummer. Indstil nu count=2 for hver gang pop() foran i køen og tilføj '2' i poppet tal og øg count++ if (count==k) så udskriv aktuelle Bomnummer ellers tilføj '3' i det viste tal og øg count++ if (count==k) så udskriv aktuelle Bomnummer . Gentag processen, indtil vi når til K'th Bomnummer .
Denne tilgang kan ses som BFS af et træ med rod som tom streng. Venstre underordnede af hver knude har en 2 tilføjet og højre underordnet har 3 tilføjet.
Nedenfor er implementeringen af denne idé.
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>
Produktion
3332322223223222223
Tidskompleksitet: O(K)
Hjælpeplads: O(n)
Denne artikel er gennemgået af team GeeksforGeeks.
