Print all n - digit numbers whose sum of digits equals to given sum

Table of Contents#

1. Problem Statement
2. Understanding the Problem
3. Approach 1: Brute Force
4. Approach 2: Recursive Backtracking
5. Best Practices
6. Example Usage
7. Conclusion
8. References

1. Problem Statement#

Given two integers n and sum, the task is to print all n - digit numbers whose sum of digits is equal to the given sum. For example, if n = 2 and sum = 5, the numbers are 14, 23, 32, 41, and 50.

2. Understanding the Problem#

We need to generate all possible n - digit numbers and then check if the sum of their digits is equal to the given sum. However, we need to be careful with the range of numbers. An n - digit number ranges from (10^{n - 1}) to (10^{n}-1). Also, the first digit of an n - digit number cannot be 0.

3. Approach 1: Brute Force#

Concept#

The brute - force approach involves generating all n - digit numbers and then checking if the sum of their digits is equal to the given sum.

Code in Python#

def digit_sum(num):
    s = 0
    while num:
        s += num % 10
        num //= 10
    return s
 
def print_n_digit_numbers(n, target_sum):
    start = 10**(n - 1)
    end = 10**n
    for num in range(start, end):
        if digit_sum(num) == target_sum:
            print(num)
 
n = 2
sum = 5
print_n_digit_numbers(n, sum)

Explanation#

• The digit_sum function calculates the sum of digits of a given number.
• The print_n_digit_numbers function iterates through all n - digit numbers and checks if the sum of their digits is equal to the target sum. If it is, the number is printed.

Complexity Analysis#

• Time Complexity: (O(9\times10^{n - 1})) because we are iterating through all n - digit numbers.
• Space Complexity: (O(1)) because we are not using any extra space proportional to the input size.

4. Approach 2: Recursive Backtracking#

Concept#

We can use recursive backtracking to generate all possible n - digit numbers with the desired digit sum. We start with the first digit (which cannot be 0) and recursively build the remaining digits, keeping track of the remaining sum and the number of digits left.

Code in Python#

def find_numbers_util(n, sum, out, index):
    if index > n or sum < 0:
        return
    if index == n:
        if sum == 0:
            print(''.join(map(str, out)))
        return
    for i in range(10):
        if index == 0 and i == 0:
            continue
        out[index] = i
        find_numbers_util(n, sum - i, out, index + 1)
 
 
def print_n_digit_numbers_recursive(n, sum):
    out = [0] * n
    find_numbers_util(n, sum, out, 0)
 
 
n = 2
sum = 5
print_n_digit_numbers_recursive(n, sum)

Explanation#

• The find_numbers_util function is a recursive function that tries all possible digits from 0 to 9 at each position.
• If the index reaches n and the sum is 0, we have found a valid number, so we print it.
• The print_n_digit_numbers_recursive function initializes an array to store the digits and calls the find_numbers_util function.

Complexity Analysis#

• Time Complexity: (O(10^n)) in the worst case, as we are exploring all possible combinations of digits.
• Space Complexity: (O(n)) due to the recursive call stack and the array to store the digits.

5. Best Practices#

• Efficiency: The recursive backtracking approach is generally more efficient than the brute - force approach, especially for larger values of n, as it avoids generating all possible numbers and only explores the valid paths.
• Code Readability: Use meaningful variable names and comments to make the code more understandable.
• Error Handling: Add appropriate error handling, such as checking if n is a positive integer and if the sum is within the valid range.

6. Example Usage#

Let's say we want to find all 3 - digit numbers whose sum of digits is 6.

n = 3
sum = 6
print_n_digit_numbers_recursive(n, sum)

This will print all 3 - digit numbers whose digit sum is 6, such as 105, 114, 123, etc.

7. Conclusion#

In this blog, we have explored two different approaches to solve the problem of printing all n - digit numbers whose sum of digits equals a given sum. The brute - force approach is simple but less efficient, while the recursive backtracking approach is more efficient and a better choice for larger values of n. By understanding these concepts, you can apply similar techniques to solve other related problems.

8. References#

• "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
• GeeksforGeeks - https://www.geeksforgeeks.org/print-all-n-digit-numbers-with-given-sum-of-digits/