To find the smallest number with a certain number of digits (D) and a certain sum (S), we need to put the digits from 0 to 9 in a way that they add up to S while keeping the overall value as low as feasible. Students generally have trouble with this problem because they have to find a way to meet two requirements: keeping the correct number of digits and getting the exact total without leading zeros. Getting good at this is a good way to prepare for more difficult data structures and algorithms (DSA).
Also Read – Advance Data Structure and Algorithms
How to Find the Smallest Number?
Problem Statement:
Find the smallest D-digit number whose digits add up to SSS. If there isn’t such a number, return “-1.”
The purpose is to determine the smallest number. To get the “smallest” value, we need to put the smallest digits in the most important places (the left side) and the biggest digits in the least important places (the right side).
Rules to Calculate the Smallest Number Correctly
- Leading Zero Rule: The first digit cannot be 0 unless the total number of digits is 1 and the sum is 0. For any number with more than one digit, the first digit must be at least 1.
- The Sum Limit: Each digit can only be between 0 and 9. Therefore, the maximum sum possible for D digits is 9 times D. If the required sum exceeds this, no such number exists.
- The Greedy Approach: We fill the number from right to left. Putting 9s at the end of the number lets us “use up” the sum rapidly, which keeps the digits at the beginning (the higher place values) as tiny as feasible.
Brute Force Method to Find the Smallest Number
We may think of a simple brute-force solution before utilising the greedy method:
- Make all the DDD-digit numbers that are feasible.
- Check to see if the sum of the digits is SSS.
- Give back the smallest number that works
- But this method doesn’t work well:
- It checks numbers up to 10D10^D10D.
- For big DDDs, the time complexity goes up a lot.
That’s why we like the greedy method, which builds the solution directly and quickly.
Greedy Algorithm to Find the Smallest Number
To get the smallest number, do this:
- See if you can do it: For there to be a result, D must be 1 (the number is 0) if S is 0. If S is greater than 9 times D, the number can’t be made; thus, return -1. Start by taking 1 away from S. We do this to keep “1” for the most important digit so that the number doesn’t start with zero.
- Fill from the right to the left: Begin with the last digit (index D-1) and work your way to the second digit (index 1).
- If the remaining amount is more than 9, put 9 in the current position and take 9 away from the total.
- If the remaining sum is less than or equal to 9, place the sum at the current position and set the remaining sum to 0.
- Finalise the First Digit: Add the remaining sum (plus the 1 we reserved earlier) to the first digit (index 0).
Examples to Find the Smallest Number
These examples show how to determine the smallest number by distributing the sum from right to left while keeping the leftmost digit as small as possible:
| Number of Digits (D) | Required Sum (S) | Logic Applied | Result |
| 3 | 10 | 1 reserved for start. Last digit gets 9. Middle gets 0. | 109 |
| 2 | 15 | 1 reserved. Last digit gets 9. Start gets (15-9) = 6. | 69 |
| 3 | 20 | 1 reserved. Last digit 9, middle 9, start (20-18) = 2. | 299 |
| 2 | 20 | Sum exceeds 18 (9×2). | -1 |
Also Read – Introduction to Red-Black Tree
C++ Program to Find the Smallest Number
While many students look for a way to write a program to find smallest of three numbers in c, solving the digit sum problem requires a more iterative approach. Here is how you can implement this in C++:
C++
#include <iostream>
#include <vector>
using namespace std;
void findSmallest(int m, int s) {
// Basic boundary checks
if (s == 0) {
(m == 1) ? cout << 0 : cout << “-1”;
return;
}
if (s > 9 * m) {
cout << “-1”;
return;
}
int res[m];
s -= 1; // Reserve 1 for the first digit
for (int i = m – 1; i > 0; i–) {
if (s > 9) {
res[i] = 9;
s -= 9;
} else {
res[i] = s;
s = 0;
}
}
res[0] = s + 1; // Add the reserved 1 back to the first digit
for (int i = 0; i < m; i++)
cout << res[i];
}
int main() {
int s = 9, m = 2;
findSmallest(m, s);
return 0;
}
Python Approach to Find the Smallest Number
Python is often the preferred language for beginners. You may know how to discover how to find minimum value in list python without inbuilt function. This method involves going through an array. We can also apply greedy reasoning to make a list of digits to find smallest number in python using for loop.
Logic for Python Implementation
We don’t have to worry about fixed array sizes in Python, which makes it easy to keep track of our digits. We build the digits instead of using a simple Python program to discover the biggest and smallest integers in a list:
- Make a list of size D that starts out with all zeros.
- Check if the sum is valid.
- Apply the same right-to-left filling strategy using a for loop.
- Convert the list of integers into a single string for the final output.
This logic is significantly different from searching for an element, such as when you find the smallest element in an array in C. In that case, you compare existing values. Here, you are the architect creating the value from scratch.
Time and Space Complexity of the Smallest Number Algorithm
- Greedy Approach:
- Time Complexity: O(D)
- Space Complexity: O(D) (for storing digits)
- Brute Force Approach:
- Time Complexity: O(D × 10^D)
- Space Complexity: O(1)
This shows why the greedy method is far more efficient for large inputs.
Also Read – Geometric Algorithms
Why Greedy Strategy Helps Find the Smallest Number?
The greedy method is optimal here because it prioritises placing the largest possible values (9s) in the positions with the lowest weight (the ones, the tens, etc.).
If you were asked to find largest and smallest number in Python using for loop, you would notice that “smallest” always implies keeping the highest place values as low as possible. By exhausting the sum S from the right, you naturally leave the smallest possible values for the left, which is the mathematical definition of the smallest possible number for a fixed length.
Mistakes to Avoid While Finding the Smallest Number
- The Single Digit Zero: If S = 0 and D = 1, the answer is ‘0’. If S = 0 and D > 1, it is impossible because a multi-digit number cannot have a sum of zero without being all zeros (leading to leading-zero issues).
- The Maximum Sum: Always multiply D by 9 first. If S is larger than this result, stop immediately and return “-1”.
- Array Bounds: When you find the smallest element in an array, you must be careful with indices. The same applies here; ensure your loop correctly targets the end of your container and moves toward the beginning.
Difference In Finding Smallest Number vs Array Minimum
This table highlights the key difference between finding the smallest value in existing data and constructing the smallest number using a greedy approach.
| Task | Methodology | Key Keyword |
| Search Array | Comparison of existing values | find the smallest element in an array in c |
| List Min/Max | Iterative comparison | Python program to find largest and smallest number in a list |
| Digit Sum Construction | Greedy placement (Right to Left) | determine the smallest number |
FAQs
How do I determine the smallest number if the sum is very large?
If the sum S is more than 9 times the number of digits D, you can't get the smallest number. The highest total that each D digit number may have is 9 * D.
Can I use this logic to find the largest number instead?
Yes, but the reasoning changes. To get the biggest number, you fill in digits from left to right with 9s until you run out of digits or the sum is full.
Why do we subtract 1 from the sum at the start?
We take away 1 to make sure that the first digit is at least 1. This avoids the number from starting with a zero, which would breach the rule regarding how many digits it should have.
Is this different from looking for the smallest item in an array?
Yes. To find the smallest element in an array, you compare existing numbers. You are making a new number in this problem by following math rules.
Can I solve this using a Python program to find largest and smallest number in a list?
Not directly. You can use a list to keep track of the numbers you make, but the rationale for finding the smallest number in a list is for searching, not building.