Finding the smallest number whose digits sum to N

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=100&&m=1&&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);
}
}
}

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())  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;
        }
    }
}

StackExchange Code Review Q#91028, answer score: 11