Find the smallest number whose sum of digits add to a number
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];