K-й номер стрелы

Опубликовано: 20 Января, 2022

Номера штанги - это числа, состоящие только из цифр 2 и 3. Для целого числа k (0 <k <= 10 ^ 7) отобразить k-й номер штанги.
Примеры:

 Ввод: k = 2
Выход: 3

Ввод: k = 3
Выход: 22

Ввод: k = 100
Выход: 322323

Ввод: k = 1000000
Выход: 3332322223223222223
Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

Ссылка: http://www.spoj.com/problems/TSHOW1/
Идея очень проста, как «Генерация двоичных чисел». Здесь мы также используем тот же подход,
мы используем структуру данных очереди для решения этой проблемы. Сначала поставьте в очередь «2», затем «3», это два номера первой и второй стрелы соответственно. Теперь установите count = 2, каждый раз, когда pop () перед очередью, и добавьте «2» в всплывающее число и увеличьте счетчик ++ if (count == k), затем распечатайте текущий номер штанги, иначе добавьте «3» в всплывающее число и увеличьте счетчик ++ if (count == k) затем распечатайте текущий номер штанги . Повторите процесс, пока мы не дойдем до K-го числа штанги.
Этот подход можно рассматривать как BFS дерева с корнем в виде пустой строки. К левому дочернему элементу каждого узла добавлено 2, а к правому дочернему элементу - 3.

Below is the implementation of this idea. 

C++

// C++ program to find K"th Boom number
#include<bits/stdc++.h>
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;
}

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

Выход:

 3332322223223222223

Автор статьи - Шашанк Мишра (Гуллу). Эта статья рецензируется командой GeeksforGeeks.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

РЕКОМЕНДУЕМЫЕ СТАТЬИ