# 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<=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);
}
}
}

• May I suggest you to delete the original question on SO? You've got good answers here and there isn't more to say. IMHO your question on SO was fine (and should not have been closed), but it's better to have no duplicates. May 18, 2015 at 10:54
• How come your question here has the indentation screwed up but your SO question looks fine? Copy-paste error? May 18, 2015 at 10:56

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

• Just asking, do we need to use long? May 20, 2015 at 1:18
• int will do. Both M and N are smaller than 2 billion. Also, the sum of digits and number of digits will be very small numbers. May 20, 2015 at 14:57
• What is i if n =99? The lowest solution I can find is 99999999999 which will not fit in an int. You need to change int i to long i and change int num to long num in sumOfDigits and long findSolution. Jul 6, 2015 at 16:12

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.

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.

• You also need the case where N is quite small, for example M = 100 (so solutions must be > 100) and N = 1 should find the number 1,000. If M+1 has a digit sum that is too large, you'd increase the number until the last digit is 0, if that has a digit sum that is too large increase by 10 until the last digits are 00, and so on. May 18, 2015 at 14:06
• @gnasher729: IMO, M is an allowed solution. May 18, 2015 at 14:35
• From the question: "find the smallest integer that is greater than M..." May 18, 2015 at 20:11

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...

• This code appears to be completely novel and not at all a review of the OP's.
– user22048
May 18, 2015 at 21:23
• The point of this site is to have the code posted reviewed :) May 19, 2015 at 2:07
• @ArghyaChakraborty you start out with "I wrote this program..." - but thats not what code review is about. You've got a SO-ish style answer here. See Checklist or General Directions on how to write a good CR-ish answer (and follow the links from there) from the meta site for some guidance on how to write a CR style answer. Explain what is good and bad with the code that the OP posted. Show how the OP's code can be improved (rather than writing entirely new code).
– user22048
May 19, 2015 at 2:12
• The point of this site is to have the code posted reviewed by others, to get more opinions in case OP missed something. :) May 19, 2015 at 2:13
• @ArghyaChakraborty: I think you can try reading some other questions and answers in this site to see how this site is intended to work. For example: codereview.stackexchange.com/questions/59486/… codereview.stackexchange.com/questions/18592/… May 19, 2015 at 2:24

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

• Please give a more detailed description of what you have improved and how you have done it. May 18, 2015 at 15:22
• This snippet is not for JAVA...you should use && instead of 'and' also it has a lot of grooming to do... May 18, 2015 at 16:34
• This code appears to be completely novel, not runnable (and rather than &&). Please give a review of the OP's code rather than writing completely new code.
– user22048
May 18, 2015 at 21:25
• @MichaelT OP asks: "I would love to know how to increase it's efficiency" Replacing with the algorithm above will increase runtime from O(i) to O(log(i)*log(i)). May 18, 2015 at 21:59
• Then do that within the context of reviewing the OP's code rather than writing entirely new code from whole cloth. Review the existing code. Show how it is inefficient and how it can be improved. An answer that is entirely new code doesn't fit well with the focus of Code Review.
– user22048
May 18, 2015 at 22:01