Рубрики

Найти первые N чистых чисел

Учитывая целое число N , задача состоит в том, чтобы напечатать первые N- е чистые числа. Число называется чистым, если

  1. Он имеет четное количество цифр.
  2. Все цифры 4 или 5 .
  3. А число это палиндром.

Первые несколько чистых чисел: 44, 55, 4444, 4554, 5445, 5555,…

Примеры:

Input: N = 4
Output: 44 55 4444 5445

Input: N = 10
Output: 44 55 4444 4554 5445 5555 444444 454454 544445 554455

Подход: идея аналогична подходу, обсуждаемому здесь . На каждом шаге очереди мы можем сгенерировать следующее число, добавив 4 и 5 с обеих сторон, то есть конец и начало предыдущего номера:

q.push("4" + temp + "4");
q.push("5" + temp + "5");

Действуя таким образом, мы можем позаботиться о палиндромах и даже числах длины

Ниже приведена реализация вышеуказанного подхода:

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для печати первых n чистых чисел

void nPureNumbers(int n)

{

  

    queue<string> q;

    vector<string> ans;

  

    // выдвигаем стартовые два элемента

    q.push("44");

    q.push("55");

    int total = 2;

  

    // Пока сгенерированные числа меньше n

    while (ans.size() < n) {

  

        string temp = q.front();

        q.pop();

        ans.push_back(temp);

  

        q.push("4" + temp + "4");

        q.push("5" + temp + "5");

    }

  

    // Сортировка строк по их значению

    sort(ans.begin(), ans.end(), [](auto s, auto s2) {

        if (s.size() == s2.size())

            return s < s2;

        else

            return s.size() < s2.size();

    });

  

    // Вывести первые n чистых чисел

    for (auto i : ans) {

        cout << i << " ";

    }

}

  
// Код драйвера

int main()

{

    int n = 4;

  

    nPureNumbers(n);

  

    return 0;

}

Выход:

44 55 4444 5445

Рекомендуемые посты:

Найти первые N чистых чисел

0.00 (0%) 0 votes