SmallestInteger.java

import java.util.*;

public class SmallestInteger {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Step 1: Read the input number
        String number = scanner.next();
        System.out.println("Input number: " + number);
        
        // Step 2: Find the smallest possible integer
        String result = findSmallestInteger(number);
        System.out.println("Output: " + result);
        
        scanner.close();
    }
    
    public static String findSmallestInteger(String number) {
        // Step 1: Convert string to array of characters (like taking out digit cards)
        char[] digits = number.toCharArray();
        System.out.println("Original digits: " + Arrays.toString(digits));
        
        // Step 2: Sort the digits in ascending order (line up smallest to biggest)
        Arrays.sort(digits);
        System.out.println("Sorted digits: " + Arrays.toString(digits));
        
        // Step 3: Handle the special case of leading zeros
        // If first digit is 0, we need to swap it with the first non-zero digit
        if (digits[0] == '0') {
            System.out.println("Found zero at beginning - need to fix this!");
            
            // Find the first non-zero digit
            for (int i = 1; i < digits.length; i++) {
                if (digits[i] != '0') {
                    // Swap the first non-zero digit with the first position
                    char temp = digits[0];
                    digits[0] = digits[i];
                    digits[i] = temp;
                    System.out.println("After swapping: " + Arrays.toString(digits));
                    break;
                }
            }
        }
        
        // Step 4: Convert the character array back to string
        String result = new String(digits);
        return result;
    }
}

// Let's trace through the examples:

class ExampleTracer {
    public static void traceExample1() {
        System.out.println("\n=== EXAMPLE 1: 45223 ===");
        System.out.println("Step 1: Extract digits: [4, 5, 2, 2, 3]");
        System.out.println("Step 2: Sort them: [2, 2, 3, 4, 5]");
        System.out.println("Step 3: No zeros, so we're done!");
        System.out.println("Result: 22345");
    }
    
    public static void traceExample2() {
        System.out.println("\n=== EXAMPLE 2: 48903012 ===");
        System.out.println("Step 1: Extract digits: [4, 8, 9, 0, 3, 0, 1, 2]");
        System.out.println("Step 2: Sort them: [0, 0, 1, 2, 3, 4, 8, 9]");
        System.out.println("Step 3: First digit is 0! We can't start with 0.");
        System.out.println("        Find first non-zero: it's 1 at position 2");
        System.out.println("        Swap 0 and 1: [1, 0, 0, 2, 3, 4, 8, 9]");
        System.out.println("Result: 10023489");
    }
    
    public static void main(String[] args) {
        traceExample1();
        traceExample2();
    }
}