Solution: Find the Largest Number
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
class MaxNumber {public static int findSumOfDigits(int num) {int sum = 0;while (num != 0) {sum = sum + num % 10;num = num / 10;}return sum;}public static void findLargestNumber(int numberOfDigits, int sumOfDigits) {int max = 0;int startRange = (int) Math.pow(10, (numberOfDigits - 1));int endRange = (int) Math.pow(10, numberOfDigits);if (sumOfDigits == 0) {if (numberOfDigits == 1)System.out.println("Largest number is " + 0);elseSystem.out.println("Largest number is Not possible");return;}// sumOfDigits is greater than the maximum possible sum.if (sumOfDigits > 9 * numberOfDigits) {System.out.println("Largest number is Not possible");return;}while (startRange < endRange) {if (findSumOfDigits(startRange) == sumOfDigits) {if (max < startRange)max = startRange;}startRange++;}System.out.println("Largest number is " + max);}}class Main{public static void main(String[] args) {int sumOfDigits = 20;int numberOfDigits = 3;System.out.println("If sum of digits is 20 and number of digits is 3 then ");MaxNumber.findLargestNumber(numberOfDigits, sumOfDigits);System.out.println();//Example 2sumOfDigits = 100;numberOfDigits = 2;System.out.println("If sum of digits is 100 and number of digits is 2 then ");MaxNumber.findLargestNumber(numberOfDigits, sumOfDigits);}}
Explanation
A simple brute force solution would be to consider all the digits (we can filter on numberOfDigits
for slight optimization) and keep track of the maximum number by comparing them to the sumOfDigits
.
Time complexity
This solution would have a time complexity of ...