Search⌘ K
AI Features

Solution: Find the Largest Number

Explore how to find the largest number from a digit sum using two approaches: brute force and greedy algorithms. Understand the trade-offs in time complexity and learn to implement an efficient greedy method that constructs the largest number digit by digit for optimal solutions in coding interviews.

Solution #1: Brute force

Java
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(10n)O(10^n) ...