Find next number whose sum of digits is N

Question

This program takes two numbers M(<10k) and N (<100) and finds the smallest number greater than M whose sum of digits = N. Additionally, as per the question's requirements, it prints the number of digits in the printed number.

Example: M = 919 , N = 34

Required number = 7999 as 7+9+9+9 = 34

   /**
     *Takes M and N , finds the number greater than M whose sum of digits = N 
     */
    import java.util.*; 
    class MtoN
    {
        static int sumOfdigits(int n)
        {
            int sum =0 ;
            while(n!=0)
            {
                sum = sum + n%10; 
                n = n/10; 
            }
            return sum;
        }

        static int numOfdigits(int n)
        {
            String str = Integer.toString(n);
            return str.length(); 
        }

        public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);
            System.out.println("Enter M (100 to 10000)");
            int M = sc.nextInt();
            System.out.println("Enter N (less than 100)");
            int N = sc.nextInt(); 
            if(N> 100 || M>10000 || M<100)
            {
                System.out.println("INVALID INPUT");
            }
            else
            {
                for(int i = M+1 ; ; i++)
                {
                    if(sumOfdigits(i) == N)
                    {
                        System.out.println("Required Number is: "+ i);
                        System.out.println("Number of digits in it "+ numOfdigits(i));
                        break;
                    }
                }
            }
        }
    }

It works fine for smaller number but takes TOO much time for numbers like: M = 9181 and N = 99. (In fact, it doesn't even print the result on my screen...)

How do I reduce this execution time?

Answer 1

This is not a review, but an extended comment.

Thou shalt not brute force. Instead of inspecting every number larger than M (it indeed takes too much time), consider partitioning N into a sum of single digit numbers, and use these partitions to form the answer.

Notice that you don't have to inspect all the partitions. The digit composition of M gives enough leads to just construct the answer.

Answer 2

As you have observed, this is not a problem you should solve using integer data types. Instead, simply compute an array of digits, then emit that as a string.

For the particular example you cite (M=9181, N=99) what is the lowest valued 'integer' that produces a sum-of-digits of 99? According to me, it's 11 digits 9 all in a row: 99_999_999_999. Now in your rules, M is required to be < 10k, so I don't think you'll have to worry about overflowing that. Thus, make an array of 11 digits, initialize it to all zeroes, and solve your problems using this 11 element array instead of a single int or long.

Next, consider this: why is 7999 the smallest integer with SOD = 34? Because 9's advance the SOD the most, and the remainder should be in the most-significant-digit to provide the greatest reduction in value: 7999 is lower than 9799, 9979, or 9997.

For a given value of M you have two scenarios: M is less than the target number already (your first example, M=919, N=34) or M is greater than or equal to the target number (e.g., M=8000, N=34).

I think the same solution works for both: start with M, and then "fill in" SOD values by incrementing the low digits. If you have to add a digit, start at 1 and work up.