Search⌘ K

Solution: Largest Number with Given Number of Digits and Sum of Digits

Explore how to solve the problem of finding the largest number with a given number of digits and sum of digits using greedy algorithms. Understand both brute force and optimized greedy approaches, their time complexities, and how to implement the solution efficiently for coding interviews.

Solution #1: Brute Force

C++
int findSumOfDigits(int num) {
int sum = 0;
while (num != 0) {
sum = sum + num % 10;
num = num / 10;
}
return sum;
}
void findLargestNumber(int numberOfDigits, int sumOfDigits) {
int max = 0;
int startRange = pow(10, (numberOfDigits - 1));
int endRange = pow(10, numberOfDigits);
if (sumOfDigits == 0) {
if (numberOfDigits == 1)
cout << "Largest number is " << 0;
else
cout << "Largest number is Not possible";
return;
}
// sumOfDigits is greater than the maximum possible sum.
if (sumOfDigits > 9 * numberOfDigits) {
cout << "Largest number is Not possible";
return;
}
while (startRange < endRange) {
if (findSumOfDigits(startRange) == sumOfDigits) {
if (max < startRange)
max = startRange;
}
startRange++;
}
cout << "Largest number is " << max;
}
// Driver code
int main() {
int sumOfDigits = 20;
int numberOfDigits = 3;
cout << "If sum of digits is 20 and number of digits is 3 then ";
findLargestNumber(numberOfDigits, sumOfDigits);
cout << endl << endl;
//Example 2
sumOfDigits = 100;
numberOfDigits = 2;
cout << "If sum of digits is 100 and number of digits is 2 then ";
findLargestNumber(numberOfDigits, sumOfDigits);
return 0;
}

A simple Brute Force solution would be to consider all digits (we can filter on numberOfDigits for slight optimization) and keep track of the maximum number by comparing with the sumOfDigits.

Time Complexity

This solution would have a time complexity of O(10n)O(10^n) ...