Find all N-digit strictly increasing numbers (Bottom-Up and Top-Down Approach)


Find all N-digit strictly increasing numbers where N varies from [1 to 9]. If we process the number from left to right and for every pair of adjacent digits, if every digit is greater than the preceding digit, we can say that the digits are strictly increasing.


For example,


8-digit strictly increasing numbers are –

12345678 12345679 12345689 12345789 12346789 12356789 12456789 13456789 23456789
 

7-digit strictly increasing numbers are –

1234567 1234568 1234569 1234578 1234579 1234589 1234678 1234679 1234689 1234789 1235678 1235679 1235689 1235789 1236789 1245678 1245679 1245689 1245789 1246789 1256789 1345678 1345679 1345689 1345789 1346789 1356789 1456789 2345678 2345679 2345689 2345789 2346789 2356789 2456789 3456789

 


 

A simple solution would be to generate all N-digit numbers and print only those numbers that satisfies the given constraints. The complexity of this solution would be exponential.

A better solution would be to generate only those N-digit numbers that satisfies the given constraints. The idea is to use recursion. At each point in the recursion, we fill the current index with digits greater than the previous digit and recuse for the next index. There are two approaches to solve this problem-

 

1. Bottom-Up Approach –

 

In Bottom-Up Approach, we start from first index and recursively fill the digits from left to right.

C

Download   Run Code

Output:

1234567 1234568 1234569 1234578 1234579 1234589 1234678 1234679 1234689 1234789 1235678 1235679 1235689 1235789 1236789 1245678 1245679 1245689 1245789 1246789 1256789 1345678 1345679 1345689 1345789 1346789 1356789 1456789 2345678 2345679 2345689 2345789 2346789 2356789 2456789 3456789

C++

Download   Run Code

Output:

1234567 1234568 1234569 1234578 1234579 1234589 1234678 1234679 1234689 1234789 1235678 1235679 1235689 1235789 1236789 1245678 1245679 1245689 1245789 1246789 1256789 1345678 1345679 1345689 1345789 1346789 1356789 1456789 2345678 2345679 2345689 2345789 2346789 2356789 2456789 3456789

 

2. Top-Down Approach –

 

In Top-Down Approach, we start from last index and recursively fill the digits from right to left.

C

Download   Run Code

Output:

3456789 2456789 1456789 2356789 1356789 1256789 2346789 1346789 1246789 1236789 2345789 1345789 1245789 1235789 1234789 2345689 1345689 1245689 1235689 1234689 1234589 2345679 1345679 1245679 1235679 1234679 1234579 1234569 2345678 1345678 1245678 1235678 1234678 1234578 1234568 1234567

C++

Download   Run Code

Output:

3456789 2456789 1456789 2356789 1356789 1256789 2346789 1346789 1246789 1236789 2345789 1345789 1245789 1235789 1234789 2345689 1345689 1245689 1235689 1234689 1234589 2345679 1345679 1245679 1235679 1234679 1234579 1234569 2345678 1345678 1245678 1235678 1234678 1234578 1234568 1234567

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Sort by:   newest | oldest | most voted
Top Coder
Top Coder

Recursion at its best..

wpDiscuz