Рубрики

Наибольшее число, меньшее или равное n, и цифры в неубывающем порядке

Математика

Учитывая число n, найдите наибольшее число, меньшее или равное n, и цифры в неубывающем порядке.

Примеры:

Input  : n = 200
Output : 199
If the given number is 200, the largest 
number which is smaller or equal to it 
having digits in non decreasing order is
199.

Input  : n = 139
Output : 139

Метод 1 (грубая сила)
Начните с n, для каждого номера проверяйте, если его цифры находятся в не убывающем порядке. Если да, то вернитесь. Иначе проверяйте чек на следующий номер, пока не найдем результат.

C ++

/ * C ++ программа для подхода грубой силы, чтобы найти

   наибольшее число, имеющее цифры в порядке убывания

   заказ. * /

#include<bits/stdc++.h>

using namespace std;

  
// Возвращает нужное число

long long nondecdigits(long long n)

{

    / * цикл, чтобы рекурсивно проверять числа меньше

       чем или равно данному числу * /

    long long int x = 0;

    for (x=n; x>=1; x--)

    {

        int no = x;

        int prev_dig = 11;

  

        // Сохраняем обходные цифры от

        // справа налево. За каждую цифру

        // проверяем, меньше ли он чем prev_dig

        bool flag = true;

        while (no != 0)

        {

            if (prev_dig < no%10)

            {

               flag = false;

               break;

            }

            prev_dig = no % 10;

            no /= 10;

        }

  

        // Мы нашли нужный номер

        if (flag == true)

           break;

    }

  

    return x;

}

  
// Драйвер программы

int main()

{

    long long n = 200;

    cout << nondecdigits(n);

    return 0;

}

Джава

// Java-программа для грубой силы
// подход к поиску наибольшего числа
// с цифрами в порядке убывания
// заказ.

import java.io.*;

  

class GFG 

{

      
// Возвращает нужное число

static int nondecdigits(int n)

{

    // цикл для рекурсивной проверки

    // числа меньше или

    // равно заданному числу

    int x = 0;

    for (x = n; x >= 1; x--)

    {

        int no = x;

        int prev_dig = 11;

  

        // Продолжаем проходить цифры

        // справа налево. За

        // каждая цифра проверяет, если она

        // меньше чем prev_dig

        boolean flag = true;

        while (no != 0)

        {

            if (prev_dig < no % 10)

            {

                flag = false;

                break;

            }

            prev_dig = no % 10;

            no /= 10;

        }

  

        // Мы нашли

        // требуемый номер

        if (flag == true)

        break;

    }

  

    return x;

}

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

public static void main (String[] args) 

{

    int n = 200;

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

}
}

  
// Этот код предоставлен ajit

Python 3

# Python 3 программа для подхода грубой силы
# найти наибольшее число с цифрами в
# неубывающий порядок.

  
# Возвращает необходимое количество

def nondecdigits( n):

  

    '' 'цикл для рекурсивной проверки чисел

    меньше или равно заданному числу '' '

    x = 0

    for x in range(n, 0, -1):

        no = x

        prev_dig = 11

  

        # Продолжайте проходить цифры от

        # справа налево. За каждую цифру

        # проверить, меньше ли он чем prev_dig

        flag = True

        while (no != 0):

            if (prev_dig < no % 10):

                flag = False

                break

              

            prev_dig = no % 10

            no //= 10

  

        # Мы нашли нужный номер

        if (flag == True):

            break

    return x

  
Код водителя

if __name__=="__main__":

      

    n = 200

    print(nondecdigits(n))

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

C #

// C # программа для перебора
// принудительный подход к поиску
// наибольшее число, имеющее
// цифры в порядке убывания
// заказ.

using System;

  

class GFG

{
// Возвращает нужное число

static int nondecdigits(int n)

{

    // цикл до рекурсивности

    // проверяем цифры меньше

    // чем или равно заданному

    // число

    int x = 0;

    for (x = n; x >= 1; x--)

    {

        int no = x;

        int prev_dig = 11;

  

        // Продолжаем проходить цифры

        // справа налево. За

        // каждая цифра проверяет, если она

        // меньше чем prev_dig

        bool flag = true;

        while (no != 0)

        {

            if (prev_dig < no % 10)

            {

                flag = false;

                break;

            }

            prev_dig = no % 10;

            no /= 10;

        }

  

        // Мы нашли

        // требуемый номер

        if (flag == true)

        break;

    }

  

    return x;

}

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

static public void Main ()

{

    int n = 200;

    Console.WriteLine(nondecdigits(n));

}
}

  
// Этот код добавлен
// от akt_mit

PHP

<?php
// PHP-программа для перебора
// принудительный подход к поиску
// наибольшее число, имеющее
// цифры в порядке убывания
// заказ.

  
// Возвращает нужное число

function nondecdigits($n)

{

      

    / * цикл рекурсивно

       проверь номера меньше

       чем или равно

       данный номер * /

    $x = 0;

    for ($x = $n; $x >= 1; $x--)

    {

        $no = $x;

        $prev_dig = 11;

  

        // Продолжаем обход

        // цифры от

        // справа налево.

        // Для каждой цифры

        // проверить, если это

        // меньше чем prev_dig

        $flag = true;

        while ($no != 0)

        {

            if ($prev_dig < $no%10)

            {

                $flag = false;

                break;

            }

            $prev_dig = $no % 10;

            $no /= 10;

        }

  

        // Мы нашли

        // требуемый номер

        if ($flag == true)

        break;

    }

  

    return $x;

}

  

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

    $n = 200;

    echo nondecdigits($n);

      
// Этот код предоставлен ajt
?>


Выход:

199

Эффективный подход
Метод, рассмотренный выше, не очень эффективен, поскольку дает результаты только для чисел до 10 ^ 5, но если число очень велико, так что оно содержит 10 ^ 5 цифр.

Итак, мы обсудим другой метод для таких больших чисел.
Шаг 1: Сохраните цифры числа в массиве или в векторе.

Шаг 2: Начните обход массива от цифры с крайней правой позиции до крайней левой в данном номере.

Шаг 3: Если цифра больше, чем цифра справа от нее, запишите индекс этой цифры в этом массиве и уменьшите эту цифру на единицу.

Шаг 4: Продолжайте обновлять этот индекс до тех пор, пока вы полностью не пройдете массив соответственно, как обсуждалось в шаге 3

Шаг 4: Установите все цифры прямо к этому индексу как 9.

Шаг 5: Распечатайте массив, так как это необходимый номер.

Предположим, что число равно 200, цифры будут 2, 0, 0. Индекс, в котором крайняя левая цифра больше, чем правая цифра, является индексом 1 (после 1-го индекса), поэтому число в индексе 1 будет 2 — 1 = 1 и все цифры справа от него будут 9. Таким образом, окончательный массив будет 1, 9, 9. И требуемое число будет 199.

C ++

/ * C ++ программа для эффективного поиска

   наибольшее число, имеющее цифры в порядке убывания

   заказ. * /

#include<bits/stdc++.h>

using namespace std;

  
// Печатает наибольшее число меньше s и
// цифры в неубывающем порядке.

void nondecdigits(string s)

{

    long long m = s.size();

  

    / * массив для хранения цифр номера * /

    long long a[m];

  

    / * преобразование символов строки в число * /

    for (long long i=0; i<m; i++)

        a[i] = s[i] - '0';

  

    / * переменная содержит значение индекса, после которого

       все цифры установлены 9 * /

    long long level = m-1;

    for (long long i=m-1; i>0; i--)

    {

        / * Проверка состояния, если цифра

           меньше его левой цифры * /

        if (a[i] < a[i-1])

        {

            a[i-1]--;

            level=i-1;

        }

    }

  

    / * Если первая цифра равна 0, ее не нужно печатать * /

    if (a[0] != 0)

    {

        for (long long i=0; i<=level; i++)

            cout << a[i];

        for (long long i=level+1; i<m; i++)

            cout << "9";

    }

    else

    {

        for (long long i=1; i<level; i++)

            cout << a[i];

        for (long long i=level+1; i<m; i++)

            cout << "9";

    }

}

  
// Функция драйвера

int main()

{

    string n = "200";

    nondecdigits(n);

    return 0;

}

Джава

/ * Java-программа для эффективного подхода к поиску
наибольшее число, имеющее цифры в порядке убывания
заказ. * /

import java.util.*;

  

class GFG

{

      
// Печатает наибольшее число меньше s и
// цифры в неубывающем порядке.

static void nondecdigits(String s)

{

    int m = s.length();

  

    / * массив для хранения цифр номера * /

    int[] a = new int[m + 1];

  

    / * преобразование символов строки в число * /

    for (int i = 0; i < m; i++)

        a[i] = (int)s.charAt(i) - (int)'0';

  

    / * переменная содержит значение индекса, после которого

    все цифры установлены 9 * /

    int level = m - 1;

    for (int i = m - 1; i > 0; i--)

    {

        / * Проверка состояния, если цифра

        меньше его левой цифры * /

        if (a[i] < a[i - 1])

        {

            a[i - 1]--;

            level = i - 1;

        }

    }

  

    / * Если первая цифра равна 0, ее не нужно печатать * /

    if (a[0] != 0)

    {

        for (int i = 0; i <= level; i++)

            System.out.print(a[i]);

        for (int i = level + 1; i < m; i++)

            System.out.print("9");

    }

    else

    {

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

            System.out.print(a[i]);

        for (int i = level + 1; i < m; i++)

            System.out.print("9");

    }

}

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

public static void main(String[] args)

{

    String n = "200";

    nondecdigits(n);

}
}

  
// Этот код предоставлен chandan_jnu

python3

# Python3 программа для эффективного подхода к
# найти наибольшее число с цифрами в
# неубывающий порядок.

  
# Печатает наибольшее число меньше s
# и цифры в неубывающем порядке.

def nondecdigits(s): 

    m = len(s); 

  

    # массив для хранения цифр номера

    a = [0] * m; 

  

    # преобразование символов строки

    # int номер

    for i in range(m): 

        a[i] = ord(s[i]) - ord('0'); 

  

    # переменная содержит значение индекса

    # после чего все цифры устанавливаются 9

    level = m - 1; 

    for i in range(m - 1, 0, -1): 

          

        # Проверка состояния, если цифра

        # меньше его левой цифры

        if (a[i] < a[i - 1]): 

            a[i - 1] -= 1; 

            level = i - 1; 

  

    # Если первая цифра равна 0, ее не нужно печатать * /

    if (a[0] != 0):

        for i in range(level + 1): 

            print(a[i], end = ""); 

        for i in range(level + 1, m): 

            print("9", end = ""); 

    else:

        for i in range(1, level): 

            print(a[i], end = ""); 

        for i in range(level + 1, m):

            print("9", end = ""); 

  
Код водителя

n = "200"; 

nondecdigits(n); 

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

C #

/ * C # программа для эффективного подхода к поиску
наибольшее число, имеющее цифры в порядке убывания
заказ. * /

using System;

  

class GFG

{

      
// Печатает наибольшее число меньше s и
// цифры в неубывающем порядке.

static void nondecdigits(string s)

{

    int m = s.Length;

  

    / * массив для хранения цифр номера * /

    int[] a = new int[m + 1];

  

    / * преобразование символов строки в число * /

    for (int i = 0; i < m; i++)

        a[i] = (int)s[i] - (int)'0';

  

    / * переменная содержит значение индекса, после которого

    все цифры установлены 9 * /

    int level = m - 1;

    for (int i = m - 1; i > 0; i--)

    {

        / * Проверка состояния, если цифра

        меньше его левой цифры * /

        if (a[i] < a[i - 1])

        {

            a[i - 1]--;

            level = i - 1;

        }

    }

  

    / * Если первая цифра равна 0, ее не нужно печатать * /

    if (a[0] != 0)

    {

        for (int i = 0; i <= level; i++)

            Console.Write(a[i]);

        for (int i = level + 1; i < m; i++)

            Console.Write("9");

    }

    else

    {

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

            Console.Write(a[i]);

        for (int i = level + 1; i < m; i++)

            Console.Write("9");

    }

}

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

static void Main()

{

    string n = "200";

    nondecdigits(n);

}
}

  
// Этот код предоставлен chandan_jnu

PHP

<?php
/ * PHP программа для эффективного
подход, чтобы найти наибольшее число
с цифрами в порядке убывания
заказ. * /

  
// Печатает наибольшее число
// меньше чем s и цифры
// в неубывающем порядке.

function nondecdigits($s)

{

    $m = strlen($s);

  

    / * массив для хранения

    цифры номера * /

    $a[$m] = 0;

  

    / * преобразование символов

    строки int номер * /

    for ($i = 0; $i < $m; $i++)

        $a[$i] = $s[$i] - '0';

  

    / * переменная содержит

    значение индекса после

    которые все цифры установлены 9 * /

    $level = $m - 1;

    for ($i = $m - 1; $i > 0; $i--)

    {

        / * Проверка состояния

        если цифра меньше чем

        его левая цифра * /

        if ($a[$i] < $a[$i - 1])

        {

            $a[$i - 1]--;

            $level = $i - 1;

        }

    }

  

    / * Если первая цифра 0

    нет необходимости печатать его * /

    if ($a[0] != 0)

    {

        for ($i = 0; 

             $i <= $level; $i++)

            echo $a[$i];

        for ($i = $level + 1;

             $i < $m; $i++)

            echo "9";

    }

    else

    {

        for ($i = 1; $i < $level; $i++)

            echo $a[$i];

        for ($i = $level + 1; 

             $i < $m; $i++)

                echo "9";

    }

}

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

$n = "200";

nondecdigits($n);

  
// Этот код добавлен
// от ajit
?>


Выход:

199

Сложность времени Сложность времени — O (d), где d — нет. цифр в номере.

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

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

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

Наибольшее число, меньшее или равное n, и цифры в неубывающем порядке

0.00 (0%) 0 votes