Рубрики

Подсчитать натуральные числа, у которых все перестановки больше этого числа

Есть некоторое натуральное число, вся перестановка которого больше или равна этому числу, например. 123, все перестановки которого (123, 231, 321) больше или равны 123.

Учитывая натуральное число n , задача состоит в том, чтобы посчитать все такие числа от 1 до n.

Примеры:

Input : n = 15.
Output : 14
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 
13, 14, 15 are the numbers whose all 
permutation is greater than the number
itself. So, output 14.

Input : n = 100.
Output : 54

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

Эффективное решение основано на следующих наблюдениях.

Наблюдение 1: от 1 до 9, все номера имеют это свойство. Итак, для n <= 9 выведите n.
Замечание 2. Число, все перестановки которого больше или равны этому числу, имеют все цифры в порядке возрастания.

Идея состоит в том, чтобы сдвинуть все числа от 1 до 9. Теперь вставьте верхний элемент, скажем topel, и попытайтесь сделать число, цифры которого расположены в порядке возрастания, а первая цифра — topel . Чтобы сделать такие числа, вторая цифра может быть от % 10 до 9. Если это число меньше n , увеличьте счетчик и поместите число в стек, иначе проигнорируйте.

Ниже приведена реализация этого подхода:

C ++

// C ++ программа для подсчета числа меньше N,
// чья вся перестановка больше или равна числу.
#include<bits/stdc++.h>

using namespace std;

  
// Возвращаем количество всех
// перестановка больше или равна числу.

int countNumber(int n)

{

    int result = 0;

  

    // Нажав от 1 до 9, потому что все числа от 1

    // до 9 имеют это свойство.

    for (int i = 1; i <= 9; i++)

    {

        stack<int> s;

        if (i <= n)

        {

            s.push(i);

            result++;

        }

  

        // взять число из стека и добавить

        // цифра меньше последней цифры

        // этого.

        while (!s.empty())

        {

            int tp = s.top();

            s.pop();

            for (int j = tp%10; j <= 9; j++)

            {

                int x = tp*10 + j;

                if (x <= n)

                {

                    s.push(x);

                    result++;

                }

            }

        }

    }

  

    return result;

}

  
// Управляемая программа

int main()

{

    int n = 15;

    cout << countNumber(n) << endl;

    return 0;

}

Джава

import java.util.Stack;

  
// Java-программа для подсчета числа меньше N,
// чья вся перестановка больше или равна числу.

class GFG {

// Возвращаем количество всех
// перестановка больше или равна числу.

  

    static int countNumber(int n) {

        int result = 0;

  

        // Нажав от 1 до 9, потому что все числа от 1

        // до 9 имеют это свойство.

        for (int i = 1; i <= 9; i++) {

            Stack<Integer> s = new Stack<>();

            if (i <= n) {

                s.push(i);

                result++;

            }

  

            // взять число из стека и добавить

            // цифра меньше последней цифры

            // этого.

            while (!s.empty()) {

                int tp = s.peek();

                s.pop();

                for (int j = tp % 10; j <= 9; j++) {

                    int x = tp * 10 + j;

                    if (x <= n) {

                        s.push(x);

                        result++;

                    }

                }

            }

        }

  

        return result;

    }

  
// Управляемая программа

    public static void main(String[] args) {

        int n = 15;

        System.out.println(countNumber(n));

  

    }

}

  
// этот код предоставлен Rajput-Ji

python3

# Python3 программа для подсчета числа меньше
# чем N, у которого вся перестановка больше
# чем или равно числу.

  
# Вернуть счетчик числа, имеющего
# вся перестановка больше или равна
# на номер.

def countNumber(n):

    result = 0

  

    # Нажатие от 1 до 9, потому что все номера

    # от 1 до 9 имеют это свойство.

    for i in range(1, 10):

        s = [] 

        if (i <= n):

            s.append(i) 

            result += 1

  

        # взять число из стека и добавить

        # цифра меньше последней цифры

        # этого.

        while len(s) != 0:

            tp = s[-1

            s.pop()

            for j in range(tp % 10, 10):

                x = tp * 10 +

                if (x <= n):

                    s.append(x) 

                    result += 1

  

    return result

  
Код водителя

if __name__ == '__main__':

  

    n = 15

    print(countNumber(n))

  
# Этот код предоставлен PranchalK

C #

// C # программа для подсчета числа меньше N,
// чья вся перестановка больше чем
// или равно числу.

using System;

using System.Collections.Generic; 

  

class GFG 

{

  
// Возвращаем счетчик числа
// имея всю перестановку больше чем
// или равно числу.

static int countNumber(int n)

    int result = 0; 

  

    // Нажав от 1 до 9, потому что все числа от 1

    // до 9 имеют это свойство.

    for (int i = 1; i <= 9; i++)

    

        Stack<int> s = new Stack<int>(); 

        if (i <= n)

        

            s.Push(i); 

            result++; 

        

  

        // взять число из стека и добавить

        // цифра меньше последней цифры

        // этого.

        while (s.Count != 0) 

        

            int tp = s.Peek(); 

            s.Pop(); 

            for (int j = tp % 10; j <= 9; j++)

            

                int x = tp * 10 + j; 

                if (x <= n) 

                

                    s.Push(x); 

                    result++; 

                

            

        

    

  

    return result; 

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

public static void Main(String[] args) 

    int n = 15; 

    Console.WriteLine(countNumber(n)); 


  
// Этот код предоставлен Rajput-Ji


Выход:

14

Сложность времени: O (x) где x — количество элементов, напечатанных на выходе.

Эта статья предоставлена Anuj Chauhan . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Подсчитать натуральные числа, у которых все перестановки больше этого числа

0.00 (0%) 0 votes