Find smallest number with given number of digits and sum of digits
In certain scenarios, we may encounter a problem where we need to find the smallest number that satisfies two conditions: the number should have a specific number of digits, and the sum of its digits should be equal to a given value. This article explores the problem statement and solution that efficiently solves it.
Problem Statement
Given a target number of digits and a desired sum of digits, our objective is to find the smallest number that meets these criteria. For example, if we are asked to find the smallest 3-digit number with a sum of digits equal to 6, the solution would be 123.
Code Solution
// Java Program for
// Find smallest number with given number of digits and sum of digits
public class Permutation
{
public void smallestSumDigit(int digit, int sum)
{
if (digit < 0 || sum < 0)
{
// Invalid digit or sum
return;
}
String result = "";
if (digit == 0 && sum == 0)
{
result = "0";
}
else if (sum > 9 * digit)
{
// When sum not possible
result = "-1";
}
else
{
int value = sum - 1;
for (int index = 1; index < digit; ++index)
{
if (value > 9)
{
result = "9" + result;
value = value - 9;
}
else
{
result = value + "" + result;
value = 0;
}
}
result = (value + 1) + "" + result;
}
// Display given parameter values
System.out.println("Given digit : " + digit);
System.out.println("Given sum : " + sum);
System.out.println("Result : " + result + "\n");
}
public static void main(String[] args)
{
Permutation task = new Permutation();
// Test
task.smallestSumDigit(5, 45);
task.smallestSumDigit(6, 36);
}
}Output
Given digit : 5
Given sum : 45
Result : 99999
Given digit : 6
Given sum : 36
Result : 108999
// Include header file
#include <iostream>
using namespace std;
// C++ Program for
// Find smallest number with given number of digits and sum of digits
class Permutation
{
public: void smallestSumDigit(int digit, int sum)
{
if (digit < 0 || sum < 0)
{
// Invalid digit or sum
return;
}
string result = "";
if (digit == 0 && sum == 0)
{
result = "0";
}
else if (sum > 9 * digit)
{
// When sum not possible
result = "-1";
}
else
{
int value = sum - 1;
for (int index = 1; index < digit; ++index)
{
if (value > 9)
{
result = "9"
+ result;
value = value - 9;
}
else
{
result = to_string(value) + result;
value = 0;
}
}
result = to_string((value + 1)) + result;
}
// Display given parameter values
cout << "Given digit : " << digit << endl;
cout << "Given sum : " << sum << endl;
cout << "Result : " << result << endl << endl;
}
};
int main()
{
Permutation *task = new Permutation();
// Test
task->smallestSumDigit(5, 45);
task->smallestSumDigit(6, 36);
return 0;
}Output
Given digit : 5
Given sum : 45
Result : 99999
Given digit : 6
Given sum : 36
Result : 108999
package main
import "strconv"
import "fmt"
// Go Program for
// Find smallest number with given number of digits and sum of digits
type Permutation struct {}
func getPermutation() * Permutation {
var me *Permutation = &Permutation {}
return me
}
func(this Permutation) smallestSumDigit(digit, sum int) {
if digit < 0 || sum < 0 {
// Invalid digit or sum
return
}
var result string = ""
if digit == 0 && sum == 0 {
result = "0"
} else if sum > 9 * digit {
// When sum not possible
result = "-1"
} else {
var value int = sum - 1
for index := 1 ; index < digit ; index++ {
if value > 9 {
result = "9" + result
value = value - 9
} else {
result = strconv.Itoa(value) + result
value = 0
}
}
result = strconv.Itoa((value + 1)) + result
}
// Display given parameter values
fmt.Println("Given digit : ", digit)
fmt.Println("Given sum : ", sum)
fmt.Println("Result : ", result, "\n")
}
func main() {
var task * Permutation = getPermutation()
// Test
task.smallestSumDigit(5, 45)
task.smallestSumDigit(6, 36)
}Output
Given digit : 5
Given sum : 45
Result : 99999
Given digit : 6
Given sum : 36
Result : 108999
// Include namespace system
using System;
// Csharp Program for
// Find smallest number with given number of digits and sum of digits
public class Permutation
{
public void smallestSumDigit(int digit, int sum)
{
if (digit < 0 || sum < 0)
{
// Invalid digit or sum
return;
}
String result = "";
if (digit == 0 && sum == 0)
{
result = "0";
}
else if (sum > 9 * digit)
{
// When sum not possible
result = "-1";
}
else
{
int value = sum - 1;
for (int index = 1; index < digit; ++index)
{
if (value > 9)
{
result = "9" + result;
value = value - 9;
}
else
{
result = value + "" + result;
value = 0;
}
}
result = (value + 1) + "" + result;
}
// Display given parameter values
Console.WriteLine("Given digit : " + digit);
Console.WriteLine("Given sum : " + sum);
Console.WriteLine("Result : " + result + "\n");
}
public static void Main(String[] args)
{
Permutation task = new Permutation();
// Test
task.smallestSumDigit(5, 45);
task.smallestSumDigit(6, 36);
}
}Output
Given digit : 5
Given sum : 45
Result : 99999
Given digit : 6
Given sum : 36
Result : 108999
<?php
// Php Program for
// Find smallest number with given number of digits and sum of digits
class Permutation
{
public function smallestSumDigit($digit, $sum)
{
if ($digit < 0 || $sum < 0)
{
// Invalid digit or sum
return;
}
$result = "";
if ($digit == 0 && $sum == 0)
{
$result = "0";
}
else if ($sum > 9 * $digit)
{
// When sum not possible
$result = "-1";
}
else
{
$value = $sum - 1;
for ($index = 1; $index < $digit; ++$index)
{
if ($value > 9)
{
$result = "9".$result;
$value = $value - 9;
}
else
{
$result = strval($value).$result;
$value = 0;
}
}
$result = strval(($value + 1)).$result;
}
// Display given parameter values
echo("Given digit : ".$digit.
"\n");
echo("Given sum : ".$sum.
"\n");
echo("Result : ".$result.
"\n\n");
}
}
function main()
{
$task = new Permutation();
// Test
$task->smallestSumDigit(5, 45);
$task->smallestSumDigit(6, 36);
}
main();Output
Given digit : 5
Given sum : 45
Result : 99999
Given digit : 6
Given sum : 36
Result : 108999
// Node JS Program for
// Find smallest number with given number of digits and sum of digits
class Permutation
{
smallestSumDigit(digit, sum)
{
if (digit < 0 || sum < 0)
{
// Invalid digit or sum
return;
}
var result = "";
if (digit == 0 && sum == 0)
{
result = "0";
}
else if (sum > 9 * digit)
{
// When sum not possible
result = "-1";
}
else
{
var value = sum - 1;
for (var index = 1; index < digit; ++index)
{
if (value > 9)
{
result = "9" + result;
value = value - 9;
}
else
{
result = value + "" + result;
value = 0;
}
}
result = (value + 1) + "" + result;
}
// Display given parameter values
console.log("Given digit : " + digit);
console.log("Given sum : " + sum);
console.log("Result : " + result + "\n");
}
}
function main()
{
var task = new Permutation();
// Test
task.smallestSumDigit(5, 45);
task.smallestSumDigit(6, 36);
}
main();Output
Given digit : 5
Given sum : 45
Result : 99999
Given digit : 6
Given sum : 36
Result : 108999
# Python 3 Program for
# Find smallest number with given number of digits and sum of digits
class Permutation :
def smallestSumDigit(self, digit, sum) :
if (digit < 0 or sum < 0) :
# Invalid digit or sum
return
result = ""
if (digit == 0 and sum == 0) :
result = "0"
elif (sum > 9 * digit) :
# When sum not possible
result = "-1"
else :
value = sum - 1
index = 1
while (index < digit) :
if (value > 9) :
result = "9" + result
value = value - 9
else :
result = str(value) + result
value = 0
index += 1
result = str((value + 1)) + result
# Display given parameter values
print("Given digit : ", digit)
print("Given sum : ", sum)
print("Result : ", result ,"\n")
def main() :
task = Permutation()
# Test
task.smallestSumDigit(5, 45)
task.smallestSumDigit(6, 36)
if __name__ == "__main__": main()Output
Given digit : 5
Given sum : 45
Result : 99999
Given digit : 6
Given sum : 36
Result : 108999
# Ruby Program for
# Find smallest number with given number of digits and sum of digits
class Permutation
def smallestSumDigit(digit, sum)
if (digit < 0 || sum < 0)
# Invalid digit or sum
return
end
result = ""
if (digit == 0 && sum == 0)
result = "0"
elsif (sum > 9 * digit)
# When sum not possible
result = "-1"
else
value = sum - 1
index = 1
while (index < digit)
if (value > 9)
result = "9"+ result
value = value - 9
else
result = value.to_s + result
value = 0
end
index += 1
end
result = (value + 1).to_s + result
end
# Display given parameter values
print("Given digit : ", digit, "\n")
print("Given sum : ", sum, "\n")
print("Result : ", result ,"\n", "\n")
end
end
def main()
task = Permutation.new()
# Test
task.smallestSumDigit(5, 45)
task.smallestSumDigit(6, 36)
end
main()Output
Given digit : 5
Given sum : 45
Result : 99999
Given digit : 6
Given sum : 36
Result : 108999
// Scala Program for
// Find smallest number with given number of digits and sum of digits
class Permutation()
{
def smallestSumDigit(digit: Int, sum: Int): Unit = {
if (digit < 0 || sum < 0)
{
// Invalid digit or sum
return;
}
var result: String = "";
if (digit == 0 && sum == 0)
{
result = "0";
}
else if (sum > 9 * digit)
{
// When sum not possible
result = "-1";
}
else
{
var value: Int = sum - 1;
var index: Int = 1;
while (index < digit)
{
if (value > 9)
{
result = "9" + result;
value = value - 9;
}
else
{
result = value.toString() + result;
value = 0;
}
index += 1;
}
result = (value + 1).toString() + result;
}
// Display given parameter values
println("Given digit : " + digit);
println("Given sum : " + sum);
println("Result : " + result + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Permutation = new Permutation();
// Test
task.smallestSumDigit(5, 45);
task.smallestSumDigit(6, 36);
}
}Output
Given digit : 5
Given sum : 45
Result : 99999
Given digit : 6
Given sum : 36
Result : 108999
// Swift 4 Program for
// Find smallest number with given number of digits and sum of digits
class Permutation
{
func smallestSumDigit(_ digit: Int, _ sum: Int)
{
if (digit < 0 || sum < 0)
{
// Invalid digit or sum
return;
}
var result: String = "";
if (digit == 0 && sum == 0)
{
result = "0";
}
else if (sum > 9 * digit)
{
// When sum not possible
result = "-1";
}
else
{
var value: Int = sum - 1;
var index: Int = 1;
while (index < digit)
{
if (value > 9)
{
result = "9" + result;
value = value - 9;
}
else
{
result = String(value) + result;
value = 0;
}
index += 1;
}
result = String((value + 1)) + result;
}
// Display given parameter values
print("Given digit : ", digit);
print("Given sum : ", sum);
print("Result : ", result ,"\n");
}
}
func main()
{
let task: Permutation = Permutation();
// Test
task.smallestSumDigit(5, 45);
task.smallestSumDigit(6, 36);
}
main();Output
Given digit : 5
Given sum : 45
Result : 99999
Given digit : 6
Given sum : 36
Result : 108999
// Kotlin Program for
// Find smallest number with given number of digits and sum of digits
class Permutation
{
fun smallestSumDigit(digit: Int, sum: Int): Unit
{
if (digit < 0 || sum < 0)
{
// Invalid digit or sum
return;
}
var result: String = "";
if (digit == 0 && sum == 0)
{
result = "0";
}
else if (sum > 9 * digit)
{
// When sum not possible
result = "-1";
}
else
{
var value: Int = sum - 1;
var index: Int = 1;
while (index < digit)
{
if (value > 9)
{
result = "9" + result;
value = value - 9;
}
else
{
result = value.toString() + result;
value = 0;
}
index += 1;
}
result = (value + 1).toString() + result;
}
// Display given parameter values
println("Given digit : " + digit);
println("Given sum : " + sum);
println("Result : " + result + "\n");
}
}
fun main(args: Array < String > ): Unit
{
val task: Permutation = Permutation();
// Test
task.smallestSumDigit(5, 45);
task.smallestSumDigit(6, 36);
}Output
Given digit : 5
Given sum : 45
Result : 99999
Given digit : 6
Given sum : 36
Result : 108999
Solution Approach:
The provided Java code demonstrates an efficient solution to the problem. Let's understand the logic step by step:
First, the code checks if the given digit or sum is invalid (negative). If either is negative, the code exits since it is not possible to find a solution.
If the digit and sum are both zero, the code assigns the result as "0." This is a special case when both the digit and sum are zero.
If the sum is greater than 9 multiplied by the digit, it is not possible to find a number that satisfies the conditions. In such cases, the code assigns the result as "-1."
Otherwise, the code proceeds to find the smallest number that meets the criteria. It iterates from the most significant digit to the least significant digit (left to right).
To obtain the smallest possible number, the code starts with the assumption that the most significant digit (leftmost digit) is one less than the given sum. This digit is stored in the variable "value."
In each iteration, the code checks if the remaining sum is greater than 9. If so, it appends "9" to the result string and subtracts 9 from the remaining sum. This ensures that the digit at that position is the maximum possible digit (9).
If the remaining sum is less than or equal to 9, the code appends the remaining sum to the result string and sets the value variable to zero, as we have exhausted the remaining sum.
Finally, after the iterations, the code appends the value (plus one) to the result string. The addition of one ensures that the number is the smallest possible number that satisfies the conditions.
The code then prints the given digit, given sum, and the computed result.
Example Output:
Let's analyze the output for the given test cases:
Test Case 1:
Given digit: 5
Given sum: 45
Result: 99999Explanation: In this case, we need a 5-digit number with a sum of digits equal to 45. The smallest possible number that satisfies these conditions is 99999.
Test Case 2:
Given digit: 6
Given sum: 36
Result: 108999Explanation: Here, we aim for a 6-digit number with a sum of digits equal to 36. The smallest number that meets these criteria is 108999.
The time complexity of the provided solution is O(d), where d is the given number of digits.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment