It may appear straightforward to find the largest number with a specific amount of digits and a certain sum of those digits, but you need to be “greedy” to make sure the value is really the biggest it can be. This problem comes up a lot in class when people talk about how to get the maximum number with a certain number of digits and a certain sum of digits. It teaches how to handle numerical limits in a smart way. It’s important to know how the rationale behind placing digits works. This article explains the algorithm, how to use it, and some edge cases for this well-known DSA problem.
Also Read – Advance Data Structure and Algorithms
How to Find the Largest Number?
Before rushing to the greedy solution, it helps to understand the main notion in a simple way.
This method makes all the numbers that can be made with the specified number of digits and checks:
- If the sum of the digits is equal to the required sum
- Choose the biggest number from the list of valid numbers.
But this method is rather wasteful:
- There are up to 10^D potential numbers for D digits.
- This makes the temporal complexity grow exponentially.
For this reason, the brute force method doesn’t work well with big inputs and is mostly effective for figuring out the problem. This is why we like the greedy method, which quickly finds the best answer.
Greedy Approach to Find the Largest Number
A greedy algorithm is the best technique to find the largest number with given number of digits and sum of digits class. In maths, the “weight” of a number depends on where it is. A digit in the hundreds place is worth more than a digit in the tens place. So, to get the biggest number, we need to put the biggest numbers in the leftmost spots (the most important areas).
Why Do We Use 9s to Build the Largest Number?
We try to fill every spot on the left with a 9 until the total is less than 9, because 9 is the biggest single-digit number. As soon as the sum is less than 9, we place the rest of the value in the next open slot. After that, all the other slots are filled with 0s to make sure there are the proper number of numbers.
Impossible Scenarios for the Largest Number
We need to find scenarios where there is no solution before we run any code:
- The total is zero: The only number that works is 0 if the sum of the digits equals 0. But if there is more than one digit, a “0-digit” number is normally not legitimate in this case unless it is made clear.
- The sum is too high: The biggest number you can make with “D” digits is $D \times 9$. It is not possible to make the number if the required total is more than this.
Also Read – Introduction to Red-Black Tree
Algorithm to Find the Largest Number
To find the maximum number, follow these logical steps:
- Check Feasibility: If the sum is 0, the answer is only possible if the number of digits is 1. If the sum is greater than 9 times the number of digits, output “Not Possible”.
- Initialise an Array: Create an array or string of size equal to the number of digits.
- Fill Greedily: Iterate from the first index (leftmost) to the last.
- Place Digits: If the remaining sum is greater than or equal to 9, place 9 at the current index and subtract 9 from the sum.
- Place Remainder: If the sum is less than 9, place the current sum value and then set all remaining positions to 0.
Smallest vs Largest Number Logic
While our focus is on the maximum number, it helps to see how it differs from finding the minimum.
| Feature | Largest Number Strategy | Smallest Number Strategy |
| Primary Goal | Maximise the leftmost digits. | Minimise the leftmost digits. |
| Starting Digit | Always try to use 9. | Use 1 at the start (to avoid leading zeros). |
| Direction | Left to right. | Right to Left. |
| Filler Digit | Use 0 at the end. | Use 9 at the end. |
Examples of Largest Number with Given Digits and Sum
Let’s look at a few examples to help us comprehend the idea better:
- Input: Two digits, nine as the sum
- Output: The answer is 90.
- Input: 3 digits, 20 as the sum
- Output: 992
- Input: 4 digits, 15 as the sum
- Output: 9600
- Input: Digits = 2, Sum = 0
- Output: Not Possible
These examples make it evident how the greedy arrangement of digits works from left to right.
Coding Solutions to Find the Largest Number
Many students search for how to find largest digit in a number in C or how to write in Python. Below are the implementations for the specific task of building the maximum number from a given sum and digit count.
Implementation in C++
C++
#include <iostream>
#include <vector>
using namespace std;
void findLargest(int digits, int sum) {
if (sum == 0) {
digits == 1 ? cout << “0” : cout << “Not possible”;
return;
}
if (sum > 9 * digits) {
cout << “Not possible”;
return;
}
int res[digits];
for (int i = 0; i < digits; i++) {
if (sum >= 9) {
res[i] = 9;
sum -= 9;
} else {
res[i] = sum;
sum = 0;
}
}
for (int i = 0; i < digits; i++) cout << res[i];
}
int main() {
findLargest(3, 20); // Output: 992
return 0;
}
Implementation in Python
If you want to write a program in Python, you can adapt the logic easily. Here is the code to find the highest number with a specific sum:
Python
def find_largest(digits, total_sum):
if total_sum == 0:
return 0 if digits == 1 else “Not possible”
if total_sum > 9 * digits:
return “Not possible”
result = [0] * digits
for i in range(digits):
if total_sum >= 9:
result[i] = 9
total_sum -= 9
else:
result[i] = total_sum
total_sum = 0
return “”.join(map(str, result))
Implementation in Java
This Java implementation follows the same greedy logic, using a StringBuilder for efficient digit construction and output formatting.
print(find_largest(4, 15)) # Output: 9600
class LargestNumber {
static String findLargest(int digits, int sum) {
if (sum == 0) {
return (digits == 1) ? “0” : “Not possible”;
}
if (sum > 9 * digits) {
return “Not possible”;
}
StringBuilder result = new StringBuilder();
for (int i = 0; i < digits; i++) {
if (sum >= 9) {
result.append(9);
sum -= 9;
} else {
result.append(sum);
sum = 0;
}
}
return result.toString();
}
public static void main(String[] args) {
System.out.println(findLargest(3, 20)); // Output: 992
}
}
Maximum and Minimum Digit in a Number
In many competitive exams, you might be asked about the maximum and minimum digits. This is slightly different from our main problem but uses similar logic. While the maximum number problem asks you to construct a value, finding the max/min digit asks you to analyse an existing one.
To find the largest digit in an existing number:
- Convert the number to a string or use the modulo operator (%) to peel off digits one by one.
- Maintain a variable max_digit and update it whenever you find a higher value.
Also Read – Geometric Algorithms
Common Mistakes While Finding the Largest Number
- Ignoring the “Not Possible” case: Always check if sum > digits * 9.
- Leading Zeros: For the biggest integer, leading zeros don’t normally matter until the sum is 0. But for the smallest integer, you need to make sure that the first digit is at least 1.
- Integer Overflow: If the number of digits is big (like 100), the number won’t fit in a regular int or long long variable. Always handle the result as a string or an array.
Key Constraints and Conditions of Largest Number
The table below summarises key scenarios to help you quickly determine whether forming the number is possible and how the digits are distributed.
| Digits (D) | Sum (S) | Possible? | Result Logic |
| 3 | 28 | No | 3 * 9 = 27 (Max possible) |
| 3 | 20 | Yes | 9, 9, 2 |
| 5 | 1 | Yes | 1, 0, 0, 0, 0 |
| 2 | 0 | No | Cannot have a 2-digit number summing to 0 |
FAQs
What is the maximum possible sum for a 4-digit number?
The maximum sum for any number is the number of digits multiplied by 9. For a 4-digit number, it is 4 x 9 = 36. If you try to find the highest number with a sum of 37 and 4 digits, it is impossible.
Is it possible to utilise this reasoning to find the smallest number?
The logic for finding the smallest number is a little different. You fill in the 9s from the right and make sure that the initial digit (the leftmost one) is at least 1 to keep the number a valid D-digit number.
What do I do with numbers that are really big, like 1000?
You can't store the result in a numeric data type if it has 1000 digits. In C++, use a std::vector and in Python, use a list to output the numbers next to each other.
Is there an easy way to get the biggest digit in a number in Python?
You can use the max() function on a string version of the number, like this: max(str(num)). In Python, this is the quickest way to write a program to find the largest digit in a given number in Python.
Why does DSA care about this problem?
This problem shows how the greedy algorithm works. It shows kids how to make the best choices in their area (such putting a 9) to get the best solution overall.