Smallest Number with Given Digit Sum Program in Java and Python
ISC 2015 Question 1 solution with algorithm, explanation, Java program and simple Python program to find the smallest number greater than M whose digit sum is N.
Download the complete ISC 2015 Computer Science Paper 2 (Practical).
Question:
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, then the smallest integer greater than 100 whose digits add up to 11 is 119.
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.
Test your program with the sample data and some random data.
Algorithm:
Step 1: Start.
Step 2: Accept the values of M and N.
Step 3: Check whether M lies from 100 to 10000 and N lies from 1 to 99.
Step 4: If either value is outside the allowed range, display INVALID INPUT and go to Step 13.
Step 5: Initialize a variable number with M + 1, because the required number must be greater than M.
Step 6: Find the sum of digits of number using a separate method.
Step 7: In the digit-sum method, repeatedly extract the last digit using remainder by 10 and add it to sum.
Step 8: Remove the last digit using division by 10 and continue until the number becomes 0.
Step 9: If the digit sum is not equal to N, increase number by 1 and repeat the digit-sum check.
Step 10: When the digit sum becomes equal to N, stop the search.
Step 11: Count the number of digits in the required number.
Step 12: Display the required number and its digit count.
Step 13: Stop.
Explanation:
The problem asks for the smallest integer greater than M whose digit sum is exactly N. This means the program cannot simply check whether M itself satisfies the condition. The search must begin from M + 1. From there, each integer is tested in increasing order. Since the numbers are checked one by one from the smallest possible candidate upwards, the first valid number found is automatically the smallest required number.
Before starting the search, the input values are validated. The question states that M must be between 100 and 10000, both inclusive, and N must be less than 100. In this solution, N is also taken as at least 1 because the question deals with positive input and a digit sum of 0 would not be meaningful for numbers greater than 100. If either value is invalid, the program stops immediately after displaying INVALID INPUT. This prevents unnecessary processing.
The digit sum is calculated using a user-defined method. In that method, the last digit of the number is obtained using n % 10. This digit is added to a running total. Then the number is divided by 10, which removes the last digit. For example, for 1699, the extracted digits are 9, 9, 6 and 1. Their sum is 25, so 1699 satisfies the condition when N = 25. This repeated remainder-and-division method is a standard ISC number-processing technique.
The program uses long for the search variable because the required number can become larger than the range of the original input variable. Once a number with the required digit sum is found, the loop ends. The number of digits is then counted by repeatedly dividing a copy of the number by 10. This keeps the digit-count logic separate from the digit-sum logic and makes the program easier to understand. The final output therefore gives both the required number and the total number of digits present in it.
Java Program:
/**
* The class Q1_ISC2015 inputs two integers M and N and prints the smallest
* integer greater than M whose sum of digits is equal to N.
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
* @Question Year : ISC Practical 2015 Question 1
*/
import java.util.Scanner;
class Q1_ISC2015
{
int sumDig(long n)
{
int sum = 0;
// Extract each digit from right to left and add it to sum.
while(n > 0)
{
int digit = (int)(n % 10);
sum = sum + digit;
n = n / 10;
}
return sum;
}
int countDig(long n)
{
int count = 0;
// Count digits by removing one digit in every pass.
while(n > 0)
{
count++;
n = n / 10;
}
return count;
}
public static void main(String args[])
{
Q1_ISC2015 ob = new Q1_ISC2015();
Scanner sc = new Scanner(System.in);
System.out.print("Enter a value of M from 100 to 10000: ");
int m = sc.nextInt();
System.out.print("Enter a value of N from 1 to 99: ");
int n = sc.nextInt();
if(m < 100 || m > 10000 || n < 1 || n > 99)
{
System.out.println("INVALID INPUT");
}
else
{
/*
* The required number must be greater than M.
* Therefore the search starts from M + 1.
*/
long number = (long)m + 1;
while(ob.sumDig(number) != n)
{
number++;
}
System.out.println("The required number = " + number);
System.out.println("Total number of digits = " + ob.countDig(number));
}
}
}Equivalent Python Program:
def sum_digits(n):
total = 0
# Extract each digit from right to left.
while n > 0:
digit = n % 10
total = total + digit
n = n // 10
return total
def count_digits(n):
count = 0
# Remove one digit in every pass and count it.
while n > 0:
count = count + 1
n = n // 10
return count
m = int(input("Enter a value of M from 100 to 10000: "))
n = int(input("Enter a value of N from 1 to 99: "))
if m < 100 or m > 10000 or n < 1 or n > 99:
print("INVALID INPUT")
else:
# The required number must be greater than M.
number = m + 1
while sum_digits(number) != n:
number = number + 1
print("The required number =", number)
print("Total number of digits =", count_digits(number))Output:
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.