
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.