Redirecting to
NADOS

Lexicographical Numbers

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a number.
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.
Input Format 
A number
Output Format 
Check the sample output and question video
Question Video
Constraints 
1 <= n <= 50000
Sample Input 
14
Sample 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






Video Solution

Code Solution

Run
 
Run
Id Name