...

/

Solution: Find the Largest Number

Solution: Find the Largest Number

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

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);
else
System.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 2
sumOfDigits = 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 O ...