Howdy coder. We are going to discuss the question, "Lexicographical Numbers" in this article.
We suggest you go through the problem link first, to get an outline of the question.
Important Link : Problem Link, Question Video Link, Solution Video Link
Lexicographical order is arranging the numbers/alphabets in a dictionary order.For example, "zeal" comes before "zen" in the dictionary because alphabetically, "a" comes before "n".
Similarly, the number 2456 comes before the number 278 lexicographically because "4" comes before "7".
Reader, meditate on the fact that the length of the strings/ numbers plays no role in such cases when determining their lexicographical order.
We understand this topic by writing the first 1000 numbers in lexicographical order as seen in figure 1.
Figure 1 shows the numbers in an increasing lexicographical order. Our order increases as we traverse through all the rows of the first column, then through all the rows of the second column and so on.
We discuss the order from the beginning. Initially, 1, 10, 100 and 1000 are in lexicographical order because they just increase their length by adding zeros to themselves.
After 1000, 101 is present because the first two digits are the same in these numbers and for the third digit "0" comes before "1" in the dictionary.
Next, notice that 11 comes 110 because the first 2 digits are the same but in the latter number we have a third digit too.
We don't have a four digit number parallel to 1000 for any other column, therefore we leave a space against it.
Can you try to write the rest of the numbers in this order yourself now?
We notice that the families of "1" come before families of "2" which come before families of "3" and so on.
In the family of "1" as well, the family of "10" comes before the family of "11" which comes before the family of "12" as marked in Figure 2.
Reader, look at figure 3 and try to comprehend this recursion tree.
Initially, we have no digits. After that comes the family of 1, then 2 , and we go upto 9.
Again, this family of 1 has families of 10, 11, 12, ... , 19 in lexicographical order. This level contains 2 digit numbers.
Next, for the next level of 3 digit numbers, 10 has a family of 100, 101, ... , 109.
This order can be understood better by comparing it with the recursion tree for alphabets from "a" to "z" as shown in figure 4.
We also suggest you watch the solution video for this portion for a better understanding.
Now that you have seen how the recursion tree for this problem works, we suggest you write the code for the same.
You can also refer to the code given below.
java;
true";
Hence a loop for 0 to 9 is applied. The dfs is carried out for the parameter 10*i +j, where 10*i helps us in getting to the next level of the tree with an increased number of digits and adding j to it helps us in traversing through the entire family.
The traversal of the recursion tree takes place as shown in figure 5.
With this we sum up our discussion of the given question. We hope it was clear to you.
Goodbye for now.
