easyDigit ProblemsJava

Form the Largest Number From the Digits of a Number

Build the largest possible integer by reordering the digits of a given number.

Quick Answer

The largest number you can build from a set of digits places the biggest digits in the highest positions. Tally the digits into an int array of size 10, then emit them from 9 down to 0 with result = result * 10 + digit. Sorting the digits in descending order is exactly what maximizes the value.

Problem Statement

Given a non-negative integer, rearrange its digits to form the largest possible number and return it. Do not convert the number to a String; use arithmetic only.

For example, from the digits of 341 the largest number is 431. From 1213 it is 3211. The key insight: the biggest number puts the largest digits in the most significant positions.

Input: A single non-negative integer n.

Output: The largest integer that can be formed by permuting the digits of n.

Examples

Example 1
Input:  341
Output: 431

Placing the biggest digit first gives 4, then 3, then 1.

Example 2
Input:  1213
Output: 3211

The digits 1, 1, 2, 3 arranged largest-first are 3, 2, 1, 1.

Constraints

  • 0 <= n <= 2,147,483,647 (fits in a 32-bit int)
  • No String conversion; arithmetic only

Think Before You Code

Reveal the questions to ask yourself first
  • To maximize a number, where should the biggest digit go — the front or the back?
  • How can you sort ten possible digit values without a comparison sort?
  • Do duplicate digits change the strategy?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
A number is larger when its high-order (leftmost) positions hold the biggest digits, so you want the digits in descending order.
Hint 2
Count each digit into an int array of length 10 using `count[n % 10]++`.
Hint 3
Rebuild by looping index 9 down to 0, appending each digit `count[d]` times with `result = result * 10 + d`.

Approach

Reveal the step-by-step approach

Maximizing the number is a greedy placement: the most significant slot should hold the largest available digit, the next slot the next largest, and so on. That is simply the digits in descending order.

  1. Tally the digits: while n is not 0, count[n % 10]++ and n = n / 10.
  2. Walk count from index 9 down to 0.
  3. Append each digit count[d] times with result = result * 10 + d.

Since the key space is the ten digits, the tally is a counting sort — no comparison sort needed.

Dry Run

Walk through the example step by step

Forming the largest number from n = 1213:

tally: count[1]=2, count[2]=1, count[3]=1

rebuild (index 9 -> 0):
index | count | result after appends
------+-------+----------------------
3     | 1     | 3
2     | 1     | 32
1     | 2     | 321, then 3211
end   |       | 3211

Solution

Reveal the full Java solution
public class LargestFromDigits {
    public static long largestNumber(int n) {
        int[] count = new int[10];
        while (n != 0) {
            count[n % 10]++;
            n /= 10;
        }
        long result = 0;
        for (int d = 9; d >= 0; d--) {
            for (int k = 0; k < count[d]; k++) {
                result = result * 10 + d;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(largestNumber(341));  // 431
        System.out.println(largestNumber(1213)); // 3211
    }
}

Greedy reasoning proves optimality: a digit contributes more to the total when it sits in a higher place value, so putting the largest digits first can never be beaten. Because only ten digit values exist, a counting-sort tally sorts them in linear time. A long accumulator avoids overflow for large inputs.

Time: O(d) where d is the number of digitsSpace: O(1) — a fixed 10-element tally

Common Mistakes

  • Emitting digits from 0 to 9, which builds the smallest number instead of the largest.
  • Dropping duplicate digits instead of appending each one count[d] times.

Edge Cases to Test

  • n = 0 returns 0.
  • Numbers that already read largest-first, like 9510, are unchanged.
  • Numbers with repeated digits, like 1213, keep every copy.

Interview Follow-Ups

  • How would you instead form the smallest number, being careful about a leading zero?
  • How would you build the largest number from the combined digits of several numbers?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us