Рубрики

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

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

Примеры :

Input  : s = 9, d = 2
Output : 18
There are many other possible numbers 
like 45, 54, 90, etc with sum of digits
as 9 and number of digits as 2. The 
smallest of them is 18.

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

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

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

C ++

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

using namespace std;

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

void findSmallest(int m, int s)

{

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

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

    if (s == 0)

    {

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

                : cout << "Not possible";

        return ;

    }

  

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

    if (s > 9*m)

    {

        cout << "Not possible";

        return ;

    }

  

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

    int res[m];

  

    // вычесть сумму на единицу для учета случаев позже

    // (Для самого значимого должно быть 1

    // цифра)

    s -= 1;

  

    // Заполняем последние цифры m-1 (справа налево)

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

    {

        // Если сумма все еще больше 9,

        // цифра должна быть 9.

        if (s > 9)

        {

            res[i] = 9;

            s -= 9;

        }

        else

        {

            res[i] = s;

            s = 0;

        }

    }

  

    // Все, что осталось, должно быть самым значительным

    // цифра

    res[0] = s + 1;  // Первоначально вычтенный 1

                     // включены здесь.

  

    cout << "Smallest number is ";

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

        cout << res[i];

}

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

int main()

{

    int s = 9, m = 2;

    findSmallest(m, s);

    return 0;

}

Джава

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

  

class GFG 

{

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

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

    static void findSmallest(int m, int s)

    {

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

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

        if (s == 0)

        {

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

              

            return ;

        }

   

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

        if (s > 9*m)

        {

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

            return ;

        }

   

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

        int[] res = new int[m];

   

        // вычесть сумму на единицу для учета случаев позже

        // (Для самого значимого должно быть 1

        // цифра)

        s -= 1;

   

        // Заполняем последние цифры m-1 (справа налево)

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

        {

            // Если сумма все еще больше 9,

            // цифра должна быть 9

            if (s > 9)

            {

                res[i] = 9;

                s -= 9;

            }

            else

            {

                res[i] = s;

                s = 0;

            }

        }

   

        // Все, что осталось, должно быть самым значительным

        // цифра

        res[0] = s + 1// Первоначально вычтенный 1

                        // включены здесь

   

        System.out.print("Smallest 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;

        findSmallest(m, s);

    }

}

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

python3

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

  

def findSmallest(m,s):

  

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

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

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

    if (s == 0):

          

        if(m == 1) :

              print("Smallest number is 0"

        else

              print("Not possible")

        return 

   

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

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

    if (s > 9*m):

      

        print("Not possible")

        return 

   

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

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

    res=[0 for i in range(m+1)]

   

    # вычесть сумму от одного до

    # учет дел позже

    # (Должно быть 1 осталось

    # для наиболее значимых

    № цифра)

    s -= 1

   

    # Заполните последние цифры m-1

    # (справа налево)

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

      

        # Если сумма все еще больше 9,

        цифра # должна быть 9.

        if (s > 9):

          

            res[i] = 9

            s -= 9

      

        else:

          

            res[i] = s

            s = 0

   

    # Все, что осталось, должно

    # быть самым значительным

    цифра

    # Первоначально вычтенный 1

    # включены здесь.

    res[0] = s + 1 

                     

   

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

    for i in range(m):

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

  

  

s = 9

m = 2

findSmallest(m, s)

  
# Этот код добавлен
# Анант Агарвал.

C #

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

using System;

  

class GFG 

{

    // Функция для печати наименьшего

    // возможное число с цифрой сумма 's'

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

    static void findSmallest(int m, int s)

    {

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

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

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

        if (s == 0)

        {

            Console.Write(m == 1 ? 

                          "Smallest number is 0"

                                  "Not possible");

              

            return ;

        }

  

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

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

        if (s > 9 * m)

        {

            Console.Write("Not possible");

            return ;

        }

  

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

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

        int []res = new int[m];

  

        // вычесть сумму на единицу на счет

        // для случаев позже (должно быть

        // 1 осталось для самого значимого

        // цифра)

        s -= 1;

  

        // Заполняем последние цифры m-1

        // (справа налево)

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

        {

            // Если сумма еще больше

            // чем 9, цифра должна быть 9

            if (s > 9)

            {

                res[i] = 9;

                s -= 9;

            }

            else

            {

                res[i] = s;

                s = 0;

            }

        }

  

        // Все, что осталось, должно быть

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

          

        // Первоначально вычтенный 1

        // включены здесь

        res[0] = s + 1; 

  

        Console.Write("Smallest number is ");

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

            Console.Write(res[i]);

    }

      

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

    public static void Main () 

    {

        int s = 9, m = 2;

        findSmallest(m, s);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

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

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

function findSmallest($m, $s)

{

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

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

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

    if ($s == 0)

    {

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

          

        echo "Smallest number is " , 0;

        else

        echo "Not possible";

        return ;

    }

  

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

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

    if ($s > 9 * $m)

    {

        echo "Not possible";

        return ;

    }

  

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

    // цифры результата int res [m];

    // вычесть сумму на единицу на счет

    // для дел позже

    // быть 1 осталось для большинства

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

    $s -= 1;

  

    // Заполняем последние цифры m-1

    // (справа налево)

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

    {

        // Если сумма еще больше

        // чем 9, цифра должна быть 9.

        if ($s > 9)

        {

            $res[$i] = 9;

            $s -= 9;

        }

        else

        {

            $res[$i] = $s;

            $s = 0;

        }

    }

  

    // Все, что осталось, должно быть

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

      

    // Первоначально вычтенный 1

    // включен сюда

    $res[0] = $s + 1; 

                        

    echo "Smallest number is ";

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

        echo $res[$i];

}

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

$s = 9; $m = 2;

findSmallest($m, $s);

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


Выход :

Smallest number is 18

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

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

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

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

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

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

0.00 (0%) 0 votes