Sponsored
Sponsored
The idea is to perform a depth-first search (DFS) to generate numbers in lexicographical order. Starting from the number 1, we explore all numbers that can be formed by appending digits from 0 to 9 as long as the generated number is less than or equal to n. If we reach a number greater than n, backtrack and explore the next number at the same level and repeat the process.
Time Complexity: O(n), Space Complexity: O(1) (excluding the output array).
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6void dfs(int current, int n, vector<int>& result) {
7 if (current > n) return;
8 result.push_back(current);
9 for (int i = 0; i <= 9; ++i) {
10 if (current * 10 + i > n) return;
11 dfs(current * 10 + i, n, result);
12 }
13}
14
15vector<int> lexicalOrder(int n) {
16 vector<int> result;
17 for (int i = 1; i < 10; ++i) {
18 dfs(i, n, result);
19 }
20 return result;
21}
22
23int main() {
24 int n = 13;
25 vector<int> result = lexicalOrder(n);
26 for (int num : result) {
27 cout << num << " ";
28 }
29 return 0;
30}This C++ solution uses depth-first search and a vector to store results. The dfs helper function recursively generates subsequent numbers by iterating over possible digits from 0 to 9 for the current level.
This iterative approach attempts to simulate the depth-first search behavior using an iterative procedure. It begins by using a number and incrementally moving to the next lexicographical number by clever digit manipulations. If a number reaches an immediate boundary, it backs off accordingly to stay within valid digits.
Time Complexity: O(n), Space Complexity: O(1) (ignoring return array).
1
This Python solution iteratively advances through potential numerals with respect to the current value and known boundaries, producing a sequence of numbers sorted lexicographically.