Рубрики

Найти наибольшее число с заданным количеством цифр и суммой цифр

Как найти наибольшее число с заданной суммой цифр s и количеством цифр d ?

Примеры:

Input  : s = 9, d = 2
Output : 90

Input  : s = 20, d = 3
Output : 992

Простое решение состоит в том, чтобы считать все числа из m цифр и отслеживать максимальное число с суммой цифр как s. Точная верхняя граница временной сложности этого решения составляет O (10 м ).

Существует жадный подход к решению проблемы. Идея состоит в том, чтобы по одному заполнить все цифры слева направо (или от самой значимой цифры к наименее значимой).
Мы сравниваем оставшуюся сумму с 9, если оставшаяся сумма больше 9, мы помещаем 9 в текущую позицию, иначе мы помещаем оставшуюся сумму. Поскольку мы заполняем цифры слева направо, мы ставим самые высокие цифры слева, поэтому получаем наибольшее число.

Ниже изображение является иллюстрацией вышеупомянутого подхода:

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

C ++

// C ++ программа для поиска наибольшего числа, которое может быть
// формируется из заданной суммы цифр и количества цифр.
#include <iostream>

using namespace std;

  
// Печатает наименьшее возможное число с цифрой sum 's'
// и 'm' количество цифр.

void findLargest(int m, int s)

{

    // Если сумма цифр равна 0, то возможен нуль

    // только если количество цифр равно 1.

    if (s == 0)

    {

        (m == 1)? cout << "Largest number is " << 0

                       : cout << "Not possible";

        return ;

    }

  

    // Сумма больше максимально возможной суммы.

    if (s > 9*m)

    {

        cout << "Not possible";

        return ;

    }

  

    // Создать массив для хранения цифр результата

    int res[m];

  

    // Заполняем от самой значимой цифры до наименьшей

    // значащая цифра.

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

    {

        // Сначала заполните 9, чтобы сделать число наибольшим

        if (s >= 9)

        {

            res[i] = 9;

            s -= 9;

        }

  

        // Если оставшаяся сумма становится меньше 9, то

        // заполняем оставшуюся сумму

        else

        {

            res[i] = s;

            s = 0;

        }

    }

  

    cout << "Largest number is ";

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

        cout << res[i];

}

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

int main()

{

    int s = 9, m = 2;

    findLargest(m, s);

    return 0;

}

Джава

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

  

class GFG 

{

    // Функция для печати максимально возможного числа с цифрой sum 's'

    // и 'm' количество цифр

    static void findLargest(int m, int s)

    {

        // Если сумма цифр равна 0, то возможно число

        // только если количество цифр равно 1

        if (s == 0)

        {

            System.out.print(m == 1 ? "Largest number is 0" : "Not possible"); 

              

            return ;

        }

   

        // Сумма больше максимально возможной суммы

        if (s > 9*m)

        {

            System.out.println("Not possible");

            return ;

        }

   

        // Создать массив для хранения цифр результата

        int[] res = new int[m];

   

        // Заполняем от самой значимой цифры до наименьшей

        // значащая цифра

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

        {

            // Сначала заполните 9, чтобы сделать число наибольшим

            if (s >= 9)

            {

                res[i] = 9;

                s -= 9;

            }

   

            // Если оставшаяся сумма становится меньше 9, то

            // заполняем оставшуюся сумму

            else

            {

                res[i] = s;

                s = 0;

            }

        }

   

        System.out.print("Largest number is ");

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

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

    }

      

    // драйверная программа

    public static void main (String[] args) 

    {

        int s = 9, m = 2;

        findLargest(m, s);

    }

}

  
// Предоставлено Прамод Кумар

python3

# Python 3 программа для поиска
# наибольшее число, которое
# может быть сформирован из данного
# сумма цифр и номера
Количество цифр.

  

  
# Печатает самые маленькие
# возможное число с цифрой
# сумма 's' и 'm' число
# цифры

def findLargest( m, s) :

  

    # Если сумма цифр равна 0,

    # тогда нубер возможен

    # только если количество цифр

    № равен 1.

    if (s == 0) :

      

        if(m == 1) :

            print("Largest number is " , "0",end = "") 

        else :

            print("Not possible",end = "")

      

        return

  

    # Сумма больше чем

    # максимально возможная сумма.

    if (s > 9 * m) :

        print("Not possible",end = "")

        return

      

    # Создать массив для

    # хранить цифры

    # результат

    res = [0] * m

  

    # Заполнить из наиболее значимых

    # цифра до наименее значимого

    цифра

    for i in range(0, m) :

          

        # Сначала заполните 9, чтобы сделать

        число наибольшее

        if (s >= 9) :

            res[i] = 9

            s = s - 9

          

        # Если оставшаяся сумма

        # становится меньше чем

        № 9, затем заполните

        # оставшаяся сумма

        else :

            res[i] = s

            s = 0

          

          

    print( "Largest number is ",end = "")

      

    for i in range(0, m) :

        print(res[i],end = "")

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

s = 9

m = 2

findLargest(m, s)

  
# Этот код предоставлен Никитой Тивари.

C #

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

using System;

  

class GFG

{

      

    // Функция для печати

    // наибольшее возможное число

    // с цифрой sum 's' и

    // 'm' количество цифр

    static void findLargest(int m, int s)

    {

        // Если сумма цифр равна 0,

        // тогда число возможно

        // только если количество цифр равно 1

        if (s == 0)

        {

            Console.Write(m == 1 ? 

                   "Largest number is 0"

                          "Not possible"); 

              

            return ;

        }

  

        // Сумма больше чем

        // максимально возможная сумма

        if (s > 9 * m)

        {

            Console.WriteLine("Not possible");

            return ;

        }

  

        // Создать массив для

        // сохраняем цифры результата

        int []res = new int[m];

  

        // Заполняем из наиболее значимых

        // цифра в младшую цифру

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

        {

            // Сначала заполните 9, чтобы сделать

            // наибольшее число

            if (s >= 9)

            {

                res[i] = 9;

                s -= 9;

            }

  

            // Если оставшаяся сумма становится

            // меньше 9, то

            // заполняем оставшуюся сумму

            else

            {

                res[i] = s;

                s = 0;

            }

        }

  

        Console.Write("Largest number is ");

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

            Console.Write(res[i]);

    }

      

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

    static public void Main ()

    {

        int s = 9, m = 2;

        findLargest(m, s);

    }

}

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

PHP

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

  
// Печатает наименьшее возможное
// число с цифрой сумма 's'
// и 'm' количество цифр.

function findLargest($m, $s)

{

    // Если сумма цифр равна 0, то

    // число возможно только если

    // количество цифр равно 1.

    if ($s == 0)

    {

        if(($m == 1) == true)

            echo "Largest number is " , 0;

        else

            echo "Not possible";

        return ;

    }

  

    // Сумма больше чем

    // максимально возможная сумма.

    if ($s > 9 * $m)

    {

        echo "Not possible";

        return ;

    }

  

    // Создать массив для хранения

    // цифры результата Fill from

    // самая значимая цифра для

    // наименее значимая цифра.

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

    {

        // Сначала заполните 9, чтобы сделать

        // наибольшее число

        if ($s >= 9)

        {

            $res[$i] = 9;

            $s -= 9;

        }

  

        // Если оставшаяся сумма становится

        // меньше 9, затем заполняем

        // оставшаяся сумма

        else

        {

            $res[$i] = $s;

            $s = 0;

        }

    }

  

    echo "Largest number is ";

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

        echo $res[$i];

}

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

$s = 9; $m = 2;

findLargest($m, $s);

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


Выход :

Largest number is 90

Сложность времени этого решения составляет O (м).

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

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

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

Найти наибольшее число с заданным количеством цифр и суммой цифр

0.00 (0%) 0 votes