386: Lexicographical-Numbers
Medium

They be recycling daily questions already??!??!? (this was the daily question on 21/09/2024)

This question is just a simple recursion problem. You can see that in the example provided with n = 13 we get:

• [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]

as the lexicographical order.

In it, it hints that the recursion equation should be, for any given i, we should have a function that iterates through all the possible digits in the ones column. Example:

• for i = 1, we have 1 to 9
• for i = 130, we have 130 to 139
• for i = 40, we have 40 to 49

Then, during this recursive function, while we iterate through all the possible digits in the ones column.

code

class Solution {
public:
    void addLexicographicalSmallest(vector<int>& ans, int current, int n) {
        for (int i = current; i <= min(current + 9, n); ++i) {
            ans.push_back(i);
            if ((i * 10) <= n) {
                addLexicographicalSmallest(ans, i*10, n);
            }
        }
    }
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        for (int i = 1; i <= min(9, n); ++i) {
            ans.push_back(i);
            if ((i * 10) <= n) {
                addLexicographicalSmallest(ans, i*10, n);
            }
        }
        return ans;
    }
};

complexity

time taken