How many positive integers from interval [m, n] have the least sum of
digits?
Input. Two integers m and n (1 ≤ m ≤ n ≤ 106).
Output. Print
the amount of positive integers from interval [m, n] with minimum sum of
digits.
|
Sample input |
Sample output |
|
1 100 |
3 |
elementary
problem
Iterate
over the numbers from m to n and find the number with
the minimum sum of digits. Store the
smallest possible sum of digits in the variable mn. Again iterate over the numbers from m to n and count the amount of numbers which sum of
digits equals to mn. The amount of such numbers will be the answer.
Algorithm
realization
Function sumd returns
the sum of sigits of number n.
int sumd(int n)
{
if (n < 10) return n;
return sumd(n / 10) + n % 10;
}
The main part of the program. Read the input data.
scanf("%d %d", &m,
&n);
The minimum sum of digits of numbers will be calculated in the variable mn. Iterate through the numbers from m to n and find the number with minimum sum of digits.
mn = 1000000000;
for (i = m; i <= n; i++)
{
temp = sumd(i);
if (temp < mn)
mn = temp;
}
Again iterate over the numbers from m to n and count the amount of numbers which
sum of digits equals to mn.
for (i = m; i <= n; i++)
if (mn ==
sumd(i)) res++;
Print the answer.
printf("%d\n", res);
Java realization
import java.util.*;
class Main
{
public static int sumd(int n)
{
if (n < 10) return n;
return sumd(n / 10) + n % 10;
}
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
int m = con.nextInt();
int n = con.nextInt();
int min = 1000000000;
for(int i = m; i <= n; i++)
{
int temp = sumd(i);
if (temp < min) min = temp;
}
int res = 0;
for(int i = m; i <= n; i++)
if (min == sumd(i)) res++;
System.out.println(res);
con.close();
}
}