Рубрики

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

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

Примеры:

Input : 38293367
Output : 98763332

Input : 1203465
Output: 6543210

Простой подход . Простой метод решения этой проблемы — извлечь и сохранить цифры данного числа в целочисленном массиве и отсортировать этот массив в порядке убывания. После сортировки массива распечатайте элементы массива.
Сложность времени : O (N log N), где N — количество цифр в данном номере.

Эффективный подход: мы знаем, что цифры в числе будут варьироваться от 0 до 9, поэтому идея состоит в том, чтобы создать хэшированный массив размером 10 и сохранить количество каждой цифры в хешированном массиве, который встречается в числе. Затем просмотрите хешированный массив от индекса 9 до 0 и рассчитайте число соответствующим образом.

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

C ++

// Программа CPP для печати максимального количества
// из набора цифр данного номера
#include <bits/stdc++.h>

using namespace std;

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

int printMaxNum(int num)

{

    // хэшированный массив для хранения количества цифр

    int count[10] = {0};

  

    // Преобразование данного числа в строку

    string str = to_string(num);

  

    // Обновление массива count

    for (int i=0; i<str.length(); i++)

        count[str[i]-'0']++;

  

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

    int result = 0, multiplier = 1;

  

    // Обход массива count

    // рассчитать максимальное количество

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

    {

        while (count[i] > 0)

        {

            result = result + (i * multiplier);

            count[i]--;

            multiplier = multiplier * 10;

        }

    }

  

    // вернуть результат

    return result;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int num = 38293367;

    cout << printMaxNum(num);

    return 0;

}

Джава

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

public class GFG

{

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

    static int printMaxNum(int num)

    {

        // хэшированный массив для хранения количества цифр

        int count[] = new int[10];

          

        // Преобразование данного числа в строку

        String str = Integer.toString(num);

          

        // Обновление массива count

        for(int i=0; i < str.length(); i++)

            count[str.charAt(i)-'0']++;

          

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

        int result = 0, multiplier = 1;

          

        // Обход массива count

        // рассчитать максимальное количество

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

        {

            while (count[i] > 0)

            {

                result = result + (i * multiplier);

                count[i]--;

                multiplier = multiplier * 10;

            }

        }

       

        // вернуть результат

        return result;

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        int num = 38293367;

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

    }

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

питон

# Программа Python для печати максимального количества
# из набора цифр данного номера

  
# Функция для печати максимального количества

def printMaximum(inum):

  

    # Хешированный массив для хранения количества цифр

    count = [0 for x in range(10)]

  

    # Преобразование данного числа в строку

    string = str(num)

  

    # Обновление массива count

    for i in range(len(string)):

        count[int(string[i])] = count[int(string[i])] +  1

  

    # Результат хранит итоговый номер

    result = 0

    multiplier = 1

  

    # обход массива count

    # рассчитать максимальное количество

  

    for i in range(10):

        while count[i] > 0:

            result = result + ( i * multiplier )

            count[i] = count[i] - 1

            multiplier = multiplier * 10

  

    # вернуть результат

    return result

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

num = 38293367

print printMaximum(num)

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

C #

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

using System;

  

class GFG 

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

static int printMaxNum(int num)

{

    // хешированный массив для хранения

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

    int []count = new int[10];

      

    // Преобразование данного числа

    // нанизывать

    String str = num.ToString();

      

    // Обновление массива count

    for(int i = 0; i < str.Length; i++)

        count[str[i] - '0']++;

      

    // результат для хранения

    // финальный номер

    int result = 0, multiplier = 1;

      

    // Обход массива count

    // рассчитать максимальное количество

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

    {

        while (count[i] > 0)

        {

            result = result + (i * multiplier);

            count[i]--;

            multiplier = multiplier * 10;

        }

    }

  

    // вернуть результат

    return result;

}

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

public static void Main() 

{

    int num = 38293367;

    Console.Write(printMaxNum(num));

}
}

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

PHP

<?php

  
// Php программа для печати максимального количества
// из набора цифр данного номера

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

function printMaxNum($num)

{

    // хэшированный массив для хранения количества цифр

    $count = array_fill(0,10, NULL);

   

    // Преобразование данного числа в строку

    $str = (string)$num;

   

    // Обновление массива count

    for ($i=0; $i<strlen($str); $i++)

        $count[ord($str[$i])-ord('0')]++;

   

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

    $result = 0;

    $multiplier = 1;

   

    // Обход массива count

    // рассчитать максимальное количество

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

    {

        while ($count[$i] > 0)

        {

            $result = $result + ($i * $multiplier);

            $count[$i]--;

            $multiplier = $multiplier * 10;

        }

    }

   

    // вернуть результат

    return $result;

}

   
// Программа драйвера для проверки вышеуказанной функции

  

    $num = 38293367;

    echo printMaxNum($num);

?>


Выход:

98763332

Сложность времени: O (N), где N — количество цифр в данном номере.
Примечание : для очень больших чисел мы можем использовать строки для ввода вместо хранения ввода в целочисленном типе данных.

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

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

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

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

0.00 (0%) 0 votes