...

/

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

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

In this review, we give a detailed analysis of the solution to the previous challenge.

Solution #1: Brute Force

Press + to interact
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(1 ...

Access this course and 1400+ top-rated courses and projects.