Рубрики

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

Найдите наименьшее число (не ведущих нулей), которое можно получить, переставив цифры данного числа.

Примеры:

Input: n = 846903
Output: 304689

Input: n = 55010
Output: 10055

Шаги, чтобы найти наименьшее число.

  1. Посчитайте частоту каждой цифры в номере.
  2. Поместите наименьшую цифру (кроме 0) слева от требуемого числа.
    и уменьшить частоту этой цифры на 1.
  3. Поместите все оставшиеся цифры в порядке возрастания слева направо.

Это решение основано на подсчете сортировки .

C ++

// C ++ программа для поиска наименьшего числа
// из цифр данного номера
#include<iostream>

using namespace std;

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

int smallest(int num)

{

    // инициализировать частоту каждой цифры в ноль

    int freq[10] = {0};

  

    // подсчитываем частоту каждой цифры в номере

    while (num)

    {

        int d = num % 10; // извлечь последнюю цифру

        freq[d]++; // приращение

        num = num / 10; // удалить последнюю цифру

    }

  

    // Устанавливаем цифру LEFTMOST на минимальное ожидаемое значение 0

    int result = 0;

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

    {

        if (freq[i])

        {

            result = i;

            freq[i]--;

            break;

        }

    }

  

    // расставляем все оставшиеся цифры

    // в порядке возрастания

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

        while (freq[i]--)

            result = result * 10 + i;

  

    return result;

}

  
// Программа для водителя

int main()

{

    int num = 570107;

    cout << smallest(num);

    return 0;

}

Джава

// Java программа для поиска наименьшего числа
// из цифр данного номера

public class GFG {

  

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

    static int smallest(int num)

    {

        // инициализировать частоту каждой цифры в ноль

        int[] freq = new int[10];

       

        // подсчитываем частоту каждой цифры в номере

        while (num > 0)

        {

            int d = num % 10; // извлечь последнюю цифру

            freq[d]++; // приращение

            num = num / 10; // удалить последнюю цифру

        }

       

        // Устанавливаем цифру LEFTMOST на минимальное ожидаемое значение 0

        int result = 0;

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

        {

            if (freq[i] != 0)

            {

                result = i;

                freq[i]--;

                break;

            }

        }

       

        // расставляем все оставшиеся цифры

        // в порядке возрастания

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

            while (freq[i]-- != 0)

                result = result * 10 + i;

       

        return result;

    }

       

    // Программа для водителя

    public static void main(String args[])

    {

        int num = 570107;

        System.out.println(smallest(num));

    }

}
// Этот код предоставлен Sumit Ghosh

питон

# Функция найти наименьшее число

def smallest(lst):

      

    # Здесь i - индекс, а n - номер списка.

    for i,n in enumerate(lst): 

          

        # Проверка первой ненулевой цифры в отсортированном списке

        if n != '0'

              

            # Удалить и сохранить цифру из списка

            tmp = lst.pop(i)

            break

      

    # Поместить первую ненулевую цифру в начало

    # и вернуть окончательный номер

    return str(tmp) + ''.join(lst) 

  

  
# Драйверная программа

if __name__ == '__main__':

      

    # Преобразование заданных чисел в строку для формирования списка

    lst = list(str(570107))

    lst.sort()

      

    # Вызов функции с использованием приведенного выше списка

    print smallest(lst)

      
# Этот код предоставлен Махендрой Ядав

C #

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

using System;

  

public class GFG {

  

    // функция для поиска наименьшего

    // число

    static int smallest(int num)

    {

          

        // инициализировать частоту

        // каждая цифра в ноль

        int[] freq = new int[10];

      

        // посчитаем частоту каждого

        // цифра в номере

        while (num > 0)

        {

              

            // извлечь последнюю цифру

            int d = num % 10;

              

            // приращение

            freq[d]++;

              

            // удалить последнюю цифру

            num = num / 10;

        }

      

        // Установить левую цифру в

        // минимальное ожидание 0

        int result = 0;

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

        {

            if (freq[i] != 0)

            {

                result = i;

                freq[i]--;

                break;

            }

        }

      

        // расставляем все оставшиеся цифры

        // в порядке возрастания

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

            while (freq[i]-- != 0)

                result = result * 10 + i;

      

        return result;

    }

      

    // Программа для водителя

    public static void Main()

    {

        int num = 570107;

        Console.WriteLine(smallest(num));

    }

}

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

PHP

<?php
// PHP программа для поиска самых маленьких
// номер из цифр данного номера

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

function smallest($num)

{

    // инициализировать частоту

    // каждая цифра в ноль

    $freq = array_fill(0, 10, 0);

  

    // посчитаем частоту каждого

    // цифра в номере

    while ($num)

    {

        $d = $num % 10; // извлечь последнюю цифру

        $freq[$d]++; // приращение

        $num = (int)($num / 10); // удалить последнюю цифру

    }

  

    // Устанавливаем левую цифру

    // к минимуму ожидаем 0

    $result = 0;

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

    {

        if ($freq[$i])

        {

            $result = $i;

            $freq[$i]--;

            break;

        }

    }

  

    // расставляем все оставшиеся цифры

    // в порядке возрастания

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

        while ($freq[$i] > 0)

        {

            $result = $result * 10 + $i;

            $freq[$i] -= 1;

        }

  

    return $result;

}

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

$num = 570107;

echo smallest($num);

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


Выход:

100577

Другой подход: найти наименьшую перестановку заданного числа

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

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

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

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

0.00 (0%) 0 votes