3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ For M = 9181; N = 99, note that the sum of Long.MAX_VALUE's digits is only 88. Integer/MAX_VALUE's is only 46. You're going to need BigInteger to be able to calculate this. ints, and even longs aren't big enough to hold the required numbers. \$\endgroup\$ – Carcigenicate Jan 31 at 21:47
  • \$\begingroup\$ For one thing, you can take advantage of the fact that the sum of digits increases by only one most of the time. Only when there is a carry out of the least significant digit do you have to recalculate. \$\endgroup\$ – Bob Dalgleish Jan 31 at 22:01
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.