Smallest Formed Number

Overview

The goal is to arrange a set of single digits to form the smallest possible integer. Since the number of digits can be up to $10^5$, we need an efficient way to determine the order.

In a positional number system, the most significant digits (the leftmost ones) have the greatest impact on the total value. To minimize the number, we generally want the smallest digits in the most significant positions. This suggests a sorting-based approach. However, we must handle the constraint regarding leading zeros: a number cannot start with '0' unless the number itself is simply "0".

Brute Force

A brute force approach would involve generating all possible permutations of the input digits, filtering out those with leading zeros, and then finding the minimum value among them.

from itertools import permutations

def smallest_formed_number(digits: list[int]) -> str:
    # Generate all unique permutations
    all_perms = set(permutations(digits))
    valid_numbers = []
    
    for p in all_perms:
        # Join digits into a string
        s = "".join(map(str, p))
        # Check for leading zero constraint
        if len(s) > 1 and s[0] == '0':
            continue
        valid_numbers.append(s)
    
    # Sort strings lexicographically (shorter strings aren't an issue here as lengths are same)
    # or convert to int to find min, then back to string
    return min(valid_numbers, key=int) if valid_numbers else ""

Time complexity: O(N!) — Generating all permutations of N digits takes factorial time, which is impossible for N=10^5. Space complexity: O(N!) — Storing all permutations requires factorial space.

Optimal Approach

The optimal strategy is a Greedy Algorithm based on sorting. To make the number as small as possible:

1. Sort the digits in ascending order.
2. Handle Leading Zeros: If the smallest digit is 0 but there are non-zero digits available, the first digit of our result must be the smallest non-zero digit.
3. Concatenate: After placing that first non-zero digit, place all remaining digits (including any zeros we skipped) in ascending order.
4. Special Case: If the array consists only of zeros, the result is simply "0".

def smallest_formed_number(digits: list[int]) -> str:
    # Sort all digits in ascending order
    digits.sort()
    
    # If the smallest digit is not 0, or if there's only one digit (which is 0),
    # we can just join and return.
    if digits[0] != 0 or len(digits) == 1:
        return "".join(map(str, digits))
    
    # Find the first non-zero digit to avoid leading zeros
    first_non_zero_idx = -1
    for i in range(len(digits)):
        if digits[i] > 0:
            first_non_zero_idx = i
            break
    
    # If no non-zero digit was found, it's a list of zeros
    if first_non_zero_idx == -1:
        return "0"
    
    # Swap the first non-zero digit to the front
    # Or more simply: construct the string using that digit first, 
    # then everything else.
    res = []
    res.append(str(digits[first_non_zero_idx]))
    
    for i in range(len(digits)):
        if i == first_non_zero_idx:
            continue
        res.append(str(digits[i]))
        
    return "".join(res)

Time complexity: O(N log N) — The bottleneck is sorting the input array of size N. Space complexity: O(N) — We store the digits in a sorted list and build a result string of length N.

Edge Cases

• All Zeros: If the input is [0, 0, 0], the logic must return "0", not "000". The constraint says we must use all elements, but standard integer representation rules apply. However, based on the specific problem rule "no leading zeros unless the result is '0'", if we strictly use all elements, "000" is usually considered invalid. The provided example cases confirm that for [0, 0, 0], the target is "0".
• Single Digit: Inputs like [5] should correctly return "5".
• Already Sorted: Inputs like [1, 2, 3] should be handled without unnecessary swaps.

Fast