Finding the smallest number whose digits sum to N

Question

I tried my hand at a grade XII Board exam program:

Given two positive numbers M and N, such that M is between 100 and 10000 and N is less than 100, find the smallest integer that is greater than M and whose digits add up to N. For example, if M = 100 and N = 11, the minimum number is 119 whose digits add up to N. Write a program to accept the numbers M and N from the user and print the smallest required number whose sum of all its digits is equal to N. Also, print the total number of digits present in the required number. The program should check for the validity of the inputs and display an appropriate message for an invalid input.

I solved the program, but as a curious person, I would love to know how to increase it's efficiency, compiler time delays, and if the program could be even shorter in length. So the primary question is, what modifications need be made in my code so that it becomes more compiler-friendly and efficient?

import java.util.Scanner;
public class ISC {
static Scanner sc =new Scanner(System.in);
static int m,n; static int ndigit;
void input(){
System.out.println("Enter the value of M: ");
m = sc.nextInt();
if (m>=100&&m<=10000) {
}
else {
    System.out.println("INVALID, Enter again: ");
    while (!(m>=100&&m<=10000)){
        m = sc.nextInt();
    }
}

System.out.println("Enter the value of N: ");
n = sc.nextInt();
if (n>=1&&n<=100){
    //do nothing
}
else {
    System.out.println("INVALID INPUT, Enter again");
    while (!(n>=1&&n<=100)){
        n = sc.nextInt();
    }
 }
}
 static int sumOfDigits(int n){
int sum = 0;
String a = Integer.toString(n); int digit;
for (int i = 0; i<a.length();i++){
    digit = Integer.parseInt(Character.toString(a.charAt(i)));
    sum += digit;
  }
return sum;
}
 static int getNo(){
ndigit = 0;
for (int i = m; i<=10000;i++){
    if (sumOfDigits(i)==n){
        ndigit = (Integer.toString(i)).length();
        return i;
    }
 }
return 0;
}
 public static void main(String[] args){
ISC a = new ISC();
a.input();
if (getNo()==0) System.out.println("NO NUMBER FOUND");
else {
  System.out.println("Minimum number is: " + getNo());
  System.out.println("Total number of digits: " + ndigit);
}
}
}

Answer 1

The program should look more like this:

public static void main(String[] args) {
    int m = askInt("Enter the value of M: ", 100, 10000),
        n = askInt("Enter the value of N: ", 1, 100);
    long solution = findSolution(m, n);
    System.out.println("Minimum number is: " + solution);
    System.out.println("Total number of digits: " + numberOfDigits(solution));
}

Notable differences:

• Your program isn't object-oriented anyway, so there's no point in instantiating a and calling input() as an instance method. (Furthermore, it's weird that input(), which is an instance method, stores its results in static variables instead of instance variables.)
• There is a lot of repetition within input(). A general-purpose integer-prompting routine, used for both M and N, would be better.
• m, n, and ndigit should not be static variables, as that makes them essentially global variables. Any function in the class can alter their values as a side-effect, making your code harder to analyze — you have to read all of the code to understand any of it.
• The solution needs to be a long, in case N is large. As @OleTange pointed out, if N is 99, then the solution must be at least 99999999999, which won't fit in an int. Note that brute-force enumeration is a very poor strategy for such large numbers.

---

Here's how I would write askInt():

static int askInt(String prompt, int min, int max) {
    int result;
    System.out.println(prompt);
    while ((result = sc.nextInt()) < min || result > max) {
        System.out.println("Invalid input, enter again: ");
    }
    return result;
}

Note that it returns a value to the caller, rather than setting some variable as a side-effect.

---

Assuming that we stick with your brute-force algorithm (and indeed there is a much faster way), these functions could be improved:

static int sumOfDigits(long num) {
    int sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

static int numberOfDigits(long num) {
    return (int)Math.log10(num) + 1;
}

Arithmetic is preferable to converting numbers to strings and back. Keep in mind that the stringification process itself involves similar arithmetic operations, and therefore must be slower than arithmetic. Dealing with strings also incurs a cost for allocating memory for them.

I've chosen num as the parameter names to avoid confusion with the N in the problem statement.

---

As for the solution search itself, there are two bugs:

• The problem calls for the solution to be strictly greater than M.
• The problem does not state that the solution should be capped at 10000. (For example, given M = 10000 and N = 2, the solution should be 10001.)

public static long findSolution(int m, int n) {
    for (long i = m + 1; ; i++) {
        if (sumOfDigits(i) == n) {
            return i;
        }
    }
}

Answer 2

Your code is nearly incomprehensible due to poor formatting. For the benefit of you and other reviewers, here is your program, with no changes other than whitespace and braces:

import java.util.Scanner;

public class ISC {
    static Scanner sc = new Scanner(System.in);
    static int m, n;
    static int ndigit;

    void input() {
        System.out.println("Enter the value of M: ");
        m = sc.nextInt();
        if (m >= 100 && m <= 10000) {
        } else {
            System.out.println("INVALID, Enter again: ");
            while (!(m >= 100 && m <= 10000)) {
                m = sc.nextInt();
            }
        }

        System.out.println("Enter the value of N: ");
        n = sc.nextInt();
        if (n >= 1 && n <= 100) {
            //do nothing
        } else {
            System.out.println("INVALID INPUT, Enter again");
            while (!(n >= 1 && n <= 100)) {
                n = sc.nextInt();
            }
         }
    }

    static int sumOfDigits(int n) {
        int sum = 0;
        String a = Integer.toString(n);
        int digit;
        for (int i = 0; i < a.length(); i++) {
            digit = Integer.parseInt(Character.toString(a.charAt(i)));
            sum += digit;
        }
        return sum;
    }

    static int getNo() {
        ndigit = 0;
        for (int i = m; i <= 10000; i++) {
            if (sumOfDigits(i) == n) {
                ndigit = (Integer.toString(i)).length();
                return i;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        ISC a = new ISC();
        a.input();
        if (getNo()==0) {
            System.out.println("NO NUMBER FOUND");
        } else {
            System.out.println("Minimum number is: " + getNo());
            System.out.println("Total number of digits: " + ndigit);
        }
    }
}

In particular,

• Use consistent indentation.
• Put a space before and after every binary operator (except commas). (!(m>=100&&m<=10000)) is hard to read.
• Leave at least one blank line between functions.
• Always use braces for both if and else.

Answer 3

Beware that the solution can exceed the capacity of a 32 bits int (in the worst,case, N=99, the solution is 99999999999).

Your input loop is better written with a while (true) if ... break rather than if () ... else while () ..., less readable and with duplication of some code.

You are using a "brute force" approach, by trying all integers in the allowed range and recomputing the sum of digits from scratch. Assuming that the solution is the integer S having d digits, you will be performing about (S-M)d additions.

Anyway, assuming that the sum of the digits of M is smaller than N, the solution is quickly achieved by setting the digits to 9, starting from the right, until the sum N is reached, if I am right. This takes O(N) additions only, an important saving in most cases. (100 (1) > 109 (10) > 119 (11)).

Now if the sum of the digits of M exceeds N, the solution requires deeper analysis. You will need to modify M in such a way that its value increases while the sum its digits decreases. I have not tried that, but I wouldn't be surprised that a fast solution remained possible.

---

Update:

In the second case, you will increase the nonzero digits from the right so that they saturate and generate a carry. (14503 (13) > 14510 (11) > 14600 (11) > 15000 (6) > 60000 (6)) When the sum falls below M, you are back in the first case.

Answer 4

I wrote this program... it works really fast... It should find out the number in O(log n) if I am not mistaken :

import java.util.*;
class ISC
{
    public static void main()
    {
        Scanner sc=new Scanner(System.in);
        System.out.print("\fEnter the value of M: ");
        long m,n,x;
        m = sc.nextLong();
        if (!(m >= 100 && m <= 10000))
        {
            System.out.print("INVALID, Enter again: ");
            while (!(m >= 100 && m <= 10000)) {
                m = sc.nextLong();
            }
        }
        System.out.print("Enter the value of N: ");
        n = sc.nextLong();
        if (!(n >= 1 && n <= 100))
        {
            System.out.print("INVALID INPUT, Enter again");
            while (!(n >= 1 && n <= 100)) {
                n = sc.nextLong();
            }
        }//input
        x=m;//we assume x is the answer
        while(sum(x)>n)//the case if Sum of digits is greater than N
        {
            long i=1;
            while(x%(Math.pow(10,i))==0)i++;
            x+=Math.pow(10,i)-(x%(Math.pow(10,i)));
        }
        while(sum(x)<n)//Now Sum of digits less than or equal to N. We have to make it strictly equal
        {
            long k=n-sum(x),i=0;
            while(((long)(x%Math.pow(10,i+1)))/((long)(Math.pow(10,i)))==9)i++;
            long l=((long)(((x%Math.pow(10,i+1))/(Math.pow(10,i)))))*((long)Math.pow(10,i));
            x+=Math.min(k,9-l)*Math.pow(10,i);
        }
        System.out.println("Number is : "+x);
    }
    public static long sum(long a)//to calculate sum of digits
    {
        long b=0;
        while(a!=0)
        {
            b+=a%10;
            a/=10;
        }
        return b;
    }
}

The algorithm is as follows :
At first I assume that M is my candidate.
Then I sum the digits of M. Sum of digits of M greater than N means that we have a case like M=342 and N=2. So I have to increase M and also make the tens and hundreds places as zero. In this example, I will change 342 to 350 then check the sum then 350 to 400 then check the sum then 400 to 1000 then check the sum...

Now that Sum of digits of M is less than or equal to N, I have to increase M until the sum becomes equal to N. So first I will change the units place then hundreds place then...In the example, 1000 will be changed to 10001 and that is the answer...

Some more examples :

N=999999999,M=500

X=500
X=509
X=599
X=999
X=9999
X=99999
X=999999
X=9999999
X=99999999
X=999999999
X=9999999999
X=99999999999

Hope these examples help...

Answer 5

This should find the number in O(log(i)*log(i)). This is faster than O(i) which the OP uses and thus improves run time (as asked for "I would love to know how to increase it's efficiency").

It uses long instead of int converted to string.

Only 2 methods and around 10 lines of code are changed. The rest of the code remains the same and it therefore not included here.

static int sumOfDigits(long num) {
    int sum;
    // compute the sum as modulo 10 for each digit in num
    // T = O(log(num))
    for (sum = 0; num != 0; sum += num%10, num = num/10) { }
    return sum;
}

static int getNo() {
    long s = 9;
    while(sumOfDigits(s) <= n && s < m) {
      // O(log(n)) rounds each taking O(log(s)) => T = O(log(m)*log(m))
      s = s*10+9;
    }
    // s      = 99999... sumdigits(s) >= n
    // factor = 10000... same length as s
    // s is bigger than the wanted number 
    // and has a bigger sum than the wanted number has.
    // So now we just have to walk down towards the number.
    // We do that one decimal position at a time
    long factor = (s+1) / 10;

    while(factor != 0) {
      while(s - factor >= m && sumOfDigits(s - factor) >= n) {
        // we can subtract 1 from this decimal position
        // Max 10 rounds = O(1)*O(log(s))
        s -= factor;
      }
      // next decimal position
      // O(log(factor)) rounds => total: T = O(log(s)*log(factor))
      factor /= 10;
    }

    int i = s;
    // Below same as original code.
    if (sumOfDigits(i) == n) {
      ndigit = (Integer.toString(i)).length();
      return i;
    }
    return 0;
}