Lexicographical Numbers
1. You are given a number.Input Format
2. You have to print all the numbers from 1 to n in lexicographical order.
Note > Check out the question video and write the recursive code as it is intended without
changing signature. The judge can't force you but intends you to teach a concept.
A numberOutput Format
Check the sample output and question videoQuestion Video
1 <= n <= 50000Sample Input
14Sample Output
1
10
11
12
13
14
2
3
4
5
6
7
8
9

Editorial
When there is no character then, first the family of 1 (1,10,100,1000,...11,110,1100,...,12,...19,190,1900,....1999....) will be printed less than N, next the family of 2(2,20,20,200,2000,....,21,210,2100,..22,.....29,290,2900,.....2999) will be printed less than N and so on till 9.
The above said thing will be clearer from recursion diagram.
As we see, first we will call the recursion function for all the numbers from 1 to 9.
Then if the number is more than N, we will return, else we will print it and call the recursion function again to generate all the families for the current number.
Code Signature:
public static void dfs(int cur, int n)
cur  our current number
n  the input number till which we have to print the numbers in lexicographical order.
Code:
public class Main { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n = scn.nextInt(); for(int i = 1; i < 10;i++){ dfs(i,n); } } public static void dfs(int cur, int n){ if(cur > n){ return; } else{ System.out.println(cur); for(int i = 0;i < 10;i++){ dfs(10 * cur + i, n); } } } }
java false
Code Explained:
From the main function, we will first call the recursion function for all the numbers from 1 to 9.
Dry running the code for n = 20.
First cur will be 1, as it less than 20, it will be printed. With the help of the loop in the recursion function, we are generating the family of the current number(cur).
If cur = 1, then at next level, it will be  (1*10 + 0), (1 * 10 + 1), ..... (1 * 10 + 9).
That is 10 ,11 ,12, 13,.....19. In pre order the cur will be first 10. As it is less than 20, it will be printed. Then with the help of loop in recursion, we will call recursion function for 100,101,102,.....109. As they all are greater than 20, we will return. Similarly, next will be 11 and the family of 11. As only 11 is smaller in the family of 11, only 11 will be printed. This will happen till 19. After that 2 will be called and it will be printed. Then from the family of 2, only 20 is less than equal to 20, so it will be printed and in rest all cases, we will return. Then from the family of 3, only 3 is less than 20, so only 3 will be printed. Similarly, for 4,5, 6,..... 9 and we will have our final output.
Base Case:
When the cur will be more than n, it means we do not need to include it as it is more than n. Also, we would not consider it is family as it is family will also be greater than n.
Time Complexity O(n):
As we are calling out recursive function n * 10 times, the time complexity will be O(n).

Asked in Companies

Related Topics