Find the smallest number whose sum of digits add to a number Request for review, optimization, best practice recommendations etc.

/**
 * Find the smallest positive number whose individual digits adds to the input number.
 * eg: consider the input 14, 
 * The smallest number whose digit add to the given number is 59 ie 5 + 9 = 14.
 * 
 * Complexity: O(n), where n is the input number
 * 
 */
public class SmallestNumber {

    private SmallestNumber() {}

    private static int getIntNum(int x, int y) {
        String number = new StringBuilder().append(x).append(y).toString();
        return Integer.parseInt(number);
    }

    /**
     * Given an integer, returns the smallest positive number whose digits adds up to that number.
     * 
     * @param x the number used to find another number whose digits add up to itself
     * @returns the smallest positive number whose digits adds up to input number.
     */
    public static int getVal(int x) {
        x = Math.abs(x);
        int min = Integer.MAX_VALUE;

        for (int i = 1; i &lt;= x / 2; i++) {
            int diff = x - i;

            int p1 = getIntNum(i, diff);
            int p2 = getIntNum(diff, i);

            /**
             * http://stackoverflow.com/questions/9576557/most-efficient-way-to-
             * find-smallest-of-3-numbers-java
             */
            if (p1 &lt; min) min = p1;
            if (p2 &lt; min) min = p2;
        }
        return min;
    }

    /**
     * http://stackoverflow.com/questions/2674707/how-to-concatenate-int-values-
     * in-java
     * 
     * @param args
     */
    public static void main(String[] args) {
       int x1 = getVal(14);
       System.out.println("Expected 59, Actual: " + x1);

       int x2 = getVal(16);
       System.out.println("Expected 79, Actual: " + x2);
    }
}
I am struggling to understand your algorithm. I don't fathom why you have to go through all that work of adding digits to values when the math behind this problem is so much simpler.

The smallest value will always be a digit followed by nines. The number of nines is the number of whole times 9 divides in to the value, and the first digit is the remainder.

Mathematically this translates to like:

public static int getVal(int val) {
    val = Math.abs(val);
    int ninecount =  val / 9;
    int remainder = val % 9;
    int scale = (int)Math.pow(10, ninecount);
    int result = remainder * scale + (scale - 1);
    return result;
}


Which is an O(1) operation (or, as has been pointed out by James, the complexity of this function is dependent on the complexity of Math.pow(...,...)). If you want to keep O(1) complexity you can precompute the scale for valid ranges of ninecount. The largest possible ninecount for an int result is 9, and for a long result it is 19. This is a small data set to keep in an indexed array accessed with int scale = scales[ninecount];