...
/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.
We'll cover the following...
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;elsecout << "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 codeint 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 2sumOfDigits = 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 ...
Access this course and 1400+ top-rated courses and projects.