Smallest number

JavaView on GFG

Problem Overview

Form smallest number from given digits.

See our study guide for structured GFG and LeetCode practice.

Intuition

Form smallest number from given digits. Sort digits ascending; handle leading zeros.

Algorithm

1Sort digits ascending. If all zeros: return "0". If first digit is 0: find first non-zero, put it first.

Common Pitfalls

• For single-digit constraint: just sort and concatenate. Avoid leading zeros (edge case with multiple zeros).

Smallest number.java

Java

// Approach: Greedy. For each position pick the smallest available digit; handle leading zeros.
// Time: O(n log n) Space: O(n)
class Solution {
    public String smallestNumber(int s, int d) {
        int result = solve(s, d, 0);

        if (result >= (int) 1e8)
            return "-1";

        return String.valueOf(result);
    }

    public int solve(int s, int d, int digit) {
        if (d == 0 && s == 0)
            return digit;

        if (d == 0 || s < 0)
            return (int) 1e8;

        int take = (int) 1e8;

        for (int i = 0; i <= 9; i++) {
            if (digit == 0 && i == 0 && d != 1)
                continue;
            take = Math.min(take, solve(s - i, d - 1, digit * 10 + i));
        }

        return take;
    }
}

Was this solution helpful?