CareerCup

There is an easier solution:
void Test(int N, int k)
{
if (k > N) {return;}

for(int i = 0; i<10; i++)
{
if (k <= N)
{
cout<<k<<endl;

k *= 10;
Test(N, k);
k /= 10;
k++;
if (k%10 == 0) return;
}
}
}

To call this use Test(25, 1), for example

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
void printHelper(int i, int range){
if (i>range) return;
if (i != 0){
std::cout<<i<<std::endl;
}
int next = i*10;
if (next <=range){
for (int k = 0;k<=9 & (next+k<=range);k++){
printHelper(next+k,range);
}
}
}
void printNumber(int N){
for (int i = 1;i<10;i++){
printHelper(i,N);
}
}
int main(){
int N;
std::cin>>N;
printNumber(N);
}

~

void Print(int n)
{
    for(int i = 1; i <= 9; i ++){
        int j = 1;
        while( j <= n){
            for(int m = 0; m < j ; ++ m){
                if(m + j * i <= n){
                    cout << m + j * i << endl;
                }
            }
            j *= 10;
        }
    }
}

can you give an example

As my understanding the lexicographic order / dictionary order of numbers for the range 0 to 20 is

0 1 10 11 12 13 14 15 16 17 18 19 2 20 3 4 5 6 7 8 9

Correct me if I'm wrong...

The only thing I can think is divide numbers by multiples of 10 and then compare each result by implementing some kind of compareTO

After lot of math and paper work here is the code in C# with inline comments

O(n) time and O(1) space complexity

public void PrintNumbersInDictionaryOrder(int N)
{
    // straight forward
    if (N < 9)
    {
        for (int i = 1; i <= N; i++)
        {
            Console.WriteLine(i);
        }

        return;
    }

    int startingDigit, multiplyingFactor, loopCount, max;

    // dangerous code with lot of math :-)
    for (int index = 1; index <= 9; index++)
    {
        // prints single digit numbers
        startingDigit = index;
        Console.WriteLine(startingDigit);

        // reset variables
        multiplyingFactor = 1;
        loopCount = 1;

        while (startingDigit * 10 < N)
        {
            // 10, 100, 1000 and so on
            // 20, 200, 2000 and so on
            startingDigit = startingDigit * (int)Math.Pow(10, 1);

            // 9, 99, 999, 9999 and so on
            max = 9 * multiplyingFactor;

            // max value depends on N
            // for example, if N is 25 then max will become 5 instead of 9
            // another example, if N is 256 then max will become 56 instead of 99
            if (N - startingDigit < Math.Pow(10, loopCount))
            {
                max = N - startingDigit;
            }

            // prints 10 - 19, 100 - 199 and so on
            for (int j = 0; j <= max; j++)
            {
                Console.WriteLine(startingDigit + j);
            }

            // 1, 11, 111, 1111 and so on
            multiplyingFactor = (multiplyingFactor * 10) + 1;

            loopCount++;
        }

        // corner case to print
        // for example, if N = 10/100/1000 while loop fails to print the number
        if (startingDigit * 10 == N)
        {
            Console.WriteLine(N);
        }
    }
}

The above code gives you just the idea and it can be refactored more to reduce some Math.

The algo will be like this:

Step 1: find out the no of digits(say n)

Step 2:
for i=1 to n and digit is 1
a. i=1, print 1
b. i=2, print 10-19(next 10)
c. i=3, print 100-199(next 10^(i-1))..

step 3: repeat the step 2 for digit 2 to 9 as well..
This will give us the proper result.

def print_numbers(k, N):
    for i in range (0, 10):
        if (k+i)>N:
            break
        print (k+i)
        print_numbers((k+i)*10, N)

if __name__ == "__main__":
    try:
        N=int(raw_input('N = '))
    except ValueError:
        print "Not a number"

    for k in range (1, 10):
        if k>N:
            break
        print k
        print_numbers(k*10, N)

var limit = N;
var lexi = function(input)
{
	for (var i = 0; i< (input == 1 ? 9 : 10); i++)
	{
		var output = input + i;
		
		if (output <= limit)
		{
			console.log(output):
			lexi(output * 10);
		}
	}
}
lexi(1);

Use Recursion to Print it out. The idea is before printing the next number, exhaust all the number with the current prefix. The solution will be simple like the following one.

Also the search should blindly start from 0 and end at 9. Because if you were asked for numbers from 15 to 999, the very first number to appear will be 100 which will be missed if we start from 15 to 99.

for(int i = 0; i < 10; i ++)
{
    PrintLexicographicOrder(i, endValue);
}
void PrintLexicographicOrder(int number, int endValue)
{ 
     if(number >= startValue && number <= endValue)
         print number;
     int nextNumber = number * 10;
     if(nextNumber == 0 || nextNumber > endValue)
           return;
     
      for(int i = 0; i < 10; i ++)
     {
         PrintLexicographicOrder(nextNumber+i, endValue);
      }
}

MSD radix sort.

public class PrintLexNumbers {
public static int LIMIT = 100;
/**
* @param args
*/
public static void main(String[] args) {

boolean[] result = new boolean[LIMIT];
printLex(100, 1, result);

}

public static void printLex(int limit, int n, boolean[] result){

if(n>limit || result[n])
return;
else{
result[n]=true;
System.out.println(n);
printLex(limit, n*10, result);
}
if(n <10 || n%10 == 0){
for(int i=1;i<10;i++){
printLex(limit, n+i, result);
}
}

}

}

C#:

private static void recurse(int value)
        {
            int max;
            if ((n - value) >= 9)
                max = ((value / 10) * 10) + 9;
            else
                max = ((value / 10) * 10) + n - value;

            for(int i = value; i <= max; i++){
                Console.WriteLine("{0}",i);

                if (i * 10 <= n && i != 0)
                {
                    recurse(i * 10);
                }
            }
        }

Another solution: the idea is to simply write a "lexicographic comparator" for integers and just pass that to the language's built-in sort function (code is F#)

// Given N, print 1 .. N in lexicographic order

// integer lexicographic comparator
let lexicographic_compare num1 num2 =
    let inline ( ** ) b p = pown b p
    let inline len_minus1 num1 = (num1 |> float |> log10 |> floor |> int)
    let inline compare_digits d1 d2 =
        if d1 < d2 then -1
        elif d1 = d2 then 0
        else 1

    let rec compare_nums num1 num2 index result =
        if result <> 0 || index < 0 then result
        else
            let d1 = num1 / (10 ** index)
            let d2 = num2 / (10 ** index)
            let _result = compare_digits d1 d2
            let _num1 = num1 - d1 * (10 ** index)
            let _num2 = num2 - d2 * (10 ** index)
            compare_nums _num1 _num2 (index - 1) _result

    let len1 = len_minus1 num1
    let len2 = len_minus1 num2

    if len1 = len2 then compare_nums num1 num2 len1 0
    elif len1 < len2 then
        let _num2 = num2 / (10 ** (len2 - len1))
        let cmp = compare_nums num1 _num2 len1 0
        if cmp = 0 then -1 
        else cmp
    else // len1 > len2
        let _num1 = num1 / (10 ** (len1 - len2))
        let cmp = compare_nums _num1 num2 len2 0
        if cmp = 0 then 1
        else cmp

// test module
let print_in_lexicographic_order n =
    [|1 .. n|]
    |> Array.sortWith lexicographic_compare
    |> Array.iter (printf "%d ")
    printfn ""

You asked for lexicographic order and don't want to convert it to character strings.
But according to lexicographic order your example shows "one -> ten -> eleven and so on".
Please edit your question : "Lexicographic order" seems pretty misleading. Your example tells what is the question.

// I just write the solution in JavaScript
function list(n, m) {
var i;
for (i = n; i <= m && i < Math.floor((n + 10) / 10) * 10; i++) {
console.log(i);
if (i <= m) {
list(i * 10, m);
}
}
}
list(1, 25);

Here is the complete and simplest solution in O(n log n) time and O(n) space.
1. Generate all the numbers from 1 to n.
2. Sort the numbers, use lexicographic order while comparing.
3. Print the sorted list.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;


public class PrintLexoList {

	public void printList(int N){
		if(N <= 0)
			return;
		MyComparator myComp = new MyComparator();
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i =1 ; i<N; i++){
			list.add(i);
		}
		Collections.sort(list, myComp);
		System.out.println(list.toString());
	}
	
	class MyComparator implements Comparator<Integer>{

		@Override
		public int compare(Integer num1, Integer num2) {			
			int digitCount1 = getNumDigits(num1);
			int digitCount2 = getNumDigits(num2);			
			if (digitCount1 > digitCount2){
				num2 = (int) ((int)num2* Math.pow(10, digitCount1 - digitCount2));
			}
			else{
				num1 = (int) ((int)num1* Math.pow(10, digitCount2 - digitCount1));
			}
			if(num1 > num2)
				return 1;
			else if(num1 < num2)
				return -1;
			else if(digitCount1 > digitCount2)
				return 1;
			return -1;
				
		}
		
		private int getNumDigits(int number){			
			int digitCount = 0;
			while(number > 0){
				number = number/10;
				digitCount++;
			}
			return digitCount;
		}		
	}
	
	public static void main(String[] args) {
		System.out.println("Enter a number");
		Scanner scanner = new Scanner(System.in);		
		new PrintLexoList().printList(scanner.nextInt());
	}
}

void PrintValuesLexicographically(int n)
{
	if(n<=0)
		return;

	int val, cnt=0;

	while(cnt<=n/10)
	{
		if(cnt==0)
			printf("%d\t",cnt);
		else
		{
			printf("%d\t",cnt);
			val=cnt*10;
			for(int i=1;i<=10;i++)
			{
				printf("%d\t",val);
				val+=1;
			}			
		}
		cnt++;
	}
	printf("\n");
}

void numsInLexOrder( int limit, int sofar = 0 )
{
	for ( int d=(sofar ? 0 : 1); d<=9; d++ )
	{
		int next = sofar * 10 + d;
		if ( next <= limit )
		{
			cout << next << "\n";
			numsInLexOrder( limit, next );
		}
		else
			break;
	}
}

import java.util.ArrayList;

public class LexiSort {

public static void main(String[] args){






ArrayList<Integer> al = new ArrayList<Integer>();


int[] a = {};

for(int j=1;j<=9;j++){

for(int k=1;k<25;k++)
{

if(k%10 == j && k/10 == 0){

al.add(k);


}


else if(k/10 == j){

al.add(k);

}





}
}
//System.out.print(al.size());
for(int i=0;i<al.size();i++){


System.out.println(al.get(i));

}






}
}

void printLexico(vector<char> ch, int idx, int len)
{
	if(idx == len)
	{
		print(ch);
		return;
	}

	bool flag = true;	
	for(int i=0; i<=9; i++)
	{
		if(i==0 && idx == 0)
			continue;
		if(flag)
		{
			print(ch);
			flag=false;
		}
		ch.push_back(i+'0');
		printLexico(ch, idx+1, len);
		ch.erase(ch.begin() + (int)ch.size()-1);
	}
} 
int main()
{
	vector<char> ch;
	printLexico(ch, 0, 2);
	return 0;
}

//Call this function func(1,N) and it should print all numbers in lexicographic order
bool func(int prn, int max)
{
	if(prn>max)
	{
		return false;
	}
	cout<<prn;
	for(int i = 0; i <= 9; i++)
	{
		if(!func(prn*10+i, max))
		{
			break;
		}
	}
	return true;
}

Use radix from msd to lsd and with each radix, put bucket according to the msd recently sorted.

Use DFS
#include <iostream>

using namespace std;

void dfs(int seed, int n){
if(seed > n) return;
cout<<seed<<endl;
for(int i=0; i<=9; i++){
int newseed = seed * 10 + i;
dfs(newseed, n);
}
}

void printlexico(int n){
if(n < 1) return;
for(int i=1; i<=9; i++){
dfs(i, n);
}
}

int main()
{
printlexico(25);

return 0;
}

Use DFS

#include <iostream>

using namespace std;

void dfs(int seed, int n){
    if(seed > n) return;
    cout<<seed<<endl;
    for(int i=0; i<=9; i++){
        int newseed = seed * 10 + i;
        dfs(newseed, n);
    }
}

void printlexico(int n){
    if(n < 1) return;
    for(int i=1; i<=9; i++){
        dfs(i, n);
    }
}

int main()
{
   printlexico(25);
   
   return 0;
}

A very easy Solution:

Can be used for general case
For N=25:

void printLexi(int N)
{
int i=1,j=0,k=10;
while(k<N)
{
cout<<i;
j++;
while(k/10 == i){cout<<k; j++ ; k++; }
i++;
}
}

private void PrintLexicographicOrder1(int N, int i)
{
	if (i <= 0) return;

	for (int j = 0; j < 10 && i + j <= N; j++)
	{
		Console.WriteLine(i+j);
		PrintLexicographicOrder1(N, (i + j) * 10);
	}
}

public void PrintLexicographicOrder(int N)
{
	for (int i = 1; i < 10 && i < N; i++)
	{
		Console.WriteLine(i);
		PrintLexicographicOrder1(N, i * 10);
	}

A comparer for std::sort... Just call std::sort with it.

bool cmp(int a, int b) {
	double x = a, y = b;
	/* align x and y */
	while(x / 10 >= 1)
		x /= 10;
	while(y / 10 >= 1)
		y /= 10;
	/* distinguish N, N0 and N00... */
	if(x == y)
		return a < b ? true : false;
	return x < y ? true : false;
}

void LexNum(int n)
{
	bool em = false;
    for (int i = 1, i < 9; i++)
	{
		em =false;
	   k = i;
	   cout << k << " ";
	   while (k < n)
	   {
		k*=10;
		for (int j = 0; j < k-1, em != true; j++)
		{
			int m = k+j;
			if (m < n) cout << m << " ";
			else 
			{
			  em = true;
			}
		}
		if (em == true) 
			break;
	   }
	}
}

void Print(int p, int n){
if(p > n) return;
cout << p << endl;
for(int i = 0; i <= 9; ++i){
if(p*10 + i <= n) Print(p*10+i,n);
}
if(p < 9) Print(p+1,n);
}

static void PrintNumsInLexicographicOrder(int n)
        {
            int k;
            for (int i = 1; i <= 9; i++)
            {
                k = i;
                Console.WriteLine(k);
                if (k * 10 <= n)
                {
                    k *= 10;
                }
                else
                {
                    continue;
                }

                for (int j = 0; j <= 9; j++)
                {
                    if (k + j <= n)
                    {
                        Console.WriteLine(k + j);
                    }
                }
            }

}

static void PrintNumsInLexicographicOrder(int n)
        {
            int k;
            for (int i = 1; i <= 9; i++)
            {
                k = i;
                Console.WriteLine(k);
                if (k * 10 <= n)
                {
                    k *= 10;
                }
                else
                {
                    continue;
                }

                for (int j = 0; j <= 9; j++)
                {
                    if (k + j <= n)
                    {
                        Console.WriteLine(k + j);
                    }
                }
            }

}

for(int i=1;i<=n;i++)
{ k=i;
  printf("%d",i);
  while(k<n)
  {  
     k = k*10; 
     if(k>n)   break;
     for(m=k;m<10*(i+1);m++)
     {
         if(m<n)
         printf(" %d",m) 
	 else break;
     }
     break;
   }
}

Here's my version

void printLexicOrder(int n)
{
    if (n<=0)
    return;

    std::vector< vector<int> > buckets(10);
    int counter = 1;
    int jumpVariable=0;

    if (n<=9)
    {
        for (int i  = 1; i<=n;++i)
        {
            cout<<i<<endl;
        }
    }
    else
    {
        for(int i  =1 ; i<=9;++i)
        {
            cout<<i<<endl;
            jumpVariable = i*pow(10,counter);

            while(jumpVariable <= n)
            {
                cout<<jumpVariable++<<endl;

                if (jumpVariable%10 == 0)
                {
                    counter+=1;
                    jumpVariable=i*pow(10,counter);
                }
            }
            counter =1;
        }
    }
}

in javascript

function printit(n,N)
{
	for(var i=n+1; i< n+10; i++)
	{
		if(i>N)return;
		console.log(i);
		printit(i*10, N);
		
	}
}
printit(0,25);

public static void printLexi(int n)
{
int x=0;
for(int i=1;i<=9;i++)
{
x=i;
System.out.println(x);
x *=10;
for(int z = 0;z<10;z++)
{
if((x<=n))
{
System.out.println(x);
x++;
}
else
break;
}
}
}

jh

void outVal(int target, int cur, vector<int>& res)
{
if(cur>target)
return;

res.push_back(cur);

for(int i=0; i<=9; i++)
outVal(target, cur*10+i, res);
}

vector<int> outVal(int target)
{
vector<int> res;

for(int i=1; i<9; i++)
outVal(target, i, res);

return res;
}

public class lexicographicOrdering {

	public static void main(String[] args) {
		int N = 25, i =0 , j =0;
		for(i=1;i<=(N/10);i++){
			System.out.println(i);
			for(j=10*i;(j<(10*(i+1)))&&j<=N;j++){
				System.out.println(j);
			}
		}
	}
}

What I would do is pretty simple: put those numbers into an array and sort it, but, instead of having the common order operator to make the swap, I'd do my own, which would be like these:
Given two number, X and Y, we will find the smallests 10^powerX > X and 10^powerY > Y. After that, we would lower each of its 'power_i' to check each digit (coming from above back to 1) and check whether the actual value of every digit is the same; if it's not, we already find a difference, and only check who's bigger. If any of the numbers 'end' (by 'end' I mean we have arrived at the units) and we had no answer yet, we simply check who's greater, X or Y. I've done a code to explain better what I wanted.

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

struct DigitSort {
	int val;

	DigitSort(int N = 0): val(N) {}

	bool operator < (const DigitSort &digitSort) const {
		int X = val;
		int Y = digitSort.val;
		long long powerX = 1;
		long long powerY = 1;

		while (powerX < X) {
			powerX *= 10;
		}
		while (powerY < Y) {
			powerY *= 10;
		}

		powerX /= 10, powerY /= 10;

		while (powerX > 0 and powerY > 0) {
			int digitX = (X / powerX) % 10;
			int digitY = (Y / powerY) % 10;

			if (digitX != digitY) {
				return digitX < digitY;
			}
			powerX /= 10;
			powerY /= 10;
		}

		return X < Y;
	}
};

void build(int N) {
	vector<DigitSort> orderedDigits(N);

	for (int i = 1; i <= N; i++) {
		orderedDigits[i - 1].val = i;
	}

	sort(orderedDigits.begin(), orderedDigits.end());

	for (int i = 0; i < N; i++) {
		printf("%d\n", orderedDigits[i].val);
	}
}

int main() {
	int N;
	scanf("%d", &N);
	build(N);
	return 0;
}

function lex(n) {
function print(m) {
if (m > n) {
return;
}
console.log(m);
for (var i=0; i<=9; i++) {
print(+(m+''+i));
}
}
for (var i=1; i<=9; i++) {
print(i);
}
}
lex(120);

public class printLexiOrder 
{
    public static void main(String args[])
    {
        for(int i=1;i<10;i++)
            lexi(i,25);
    }
    public static void lexi(int x, int num)
    {
        if(x>num)
            return;
        
        System.out.println(x);
        for(int i=0;i<9;i++)
        {
                lexi((x*10+i), num);
        }
    }

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

bool lexicComp(int i, int j)
{
	int no_digit_i = log10(i);
	int no_digit_j = log10(j);
	bool isLess = i < j;
	if (no_digit_i > no_digit_j)
	{
		j = j * pow(10, (no_digit_i - no_digit_j));
		if (i == j)
			isLess = false;
		else
			isLess = i < j;
	}
	else if (no_digit_i < no_digit_j)
	{
		i = i * pow(10, (no_digit_j - no_digit_i));
		if (i == j)
			isLess = true;
		else
			isLess = i < j;
	}
	return isLess;
}
int main()
{
	int maxLimit = 1200;
	
	vector<int> theSet;
	for (int i = 0; i < maxLimit; ++i)
	{
		theSet.push_back(maxLimit - i);
	}
	sort(theSet.begin(), theSet.end(), lexicComp);
	copy(theSet.begin(), theSet.end(), ostream_iterator<int>(cout, " "));
	return 0;
}

#include<iostream>
#include<deque>
using namespace std;
int main(){
    int upper = 130;
    int temp, temp2,temp3;
    deque<int> sol;

    for (int i = 1; i<10; i++){
      cout<<i<<endl;
      temp = i*10;
      while(temp<upper){
        for(int j =0; j<(temp/i); j++){
          temp3 = temp+j;
          if(temp3>upper) break;
          cout<<temp3<<endl;
         }
        temp *= 10;
       };
    }
     
}

#include<iostream>
#include<deque>
using namespace std;
int main(){
    int upper = 130;
    int temp, temp2,temp3;
    deque<int> sol;

    for (int i = 1; i<10; i++){
      cout<<i<<endl;
      temp = i*10;
      while(temp<upper){
        for(int j =0; j<(temp/i); j++){
          temp3 = temp+j;
          if(temp3>upper) break;
          cout<<temp3<<endl;
         }
        temp *= 10;
       };
    }

}

#Run in python 2.7
# break down the number to it digits: units digit, tens digit, hundreds digits and so on. 
# From the tens digits, it actually just tens digit multiple by ten for each digit after that.

def printlexicographic(N = 25):
    if N == 0:
        print N
    if N < 10:
        for i in range(N):
            print N
    else:
        digit = N//10
        r = N%(digit*10)
        for i in range(1,digit +1):
            print i
            for j in xrange(10):
                if (i ==  digit and j == r+1):
                    break
                print i*10 + j
        for i in xrange(i+1,10):
            print i

public static void printLexographicalOrder(int num, int n) {
if (n > num)
return;
else {
System.out.println(n);
printLexographicalOrder(num, n * 10);
if (( (n + 1) / 10) % 10 != (n / 10) % 10) {
return;
} else {
printLexographicalOrder(num, n + 1);
}
}
}

{ public static void printLexographicalOrder(int num, int n) {
if (n > num)
return;
else {
System.out.println(n);
printLexographicalOrder(num, n * 10);
if (( (n + 1) / 10) % 10 != (n / 10) % 10) {
return;
} else {
printLexographicalOrder(num, n + 1);
}
}
}
}

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{	
	public static void printt(int i, int n ){
		if( i > n ) return;
		
		for( int j = 0; j<10;++j){
			if( i <= n)
				System.out.print(i + " ");
			printt(i*10,n);
			if( i + 1 == 10)
				break;
			++i;
		}
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		printt(1,25);
	}
}

public static void printt(int i, int n ){
		if( i > n ) return;
		
		for( int j = 0; j<10;++j){
			if( i <= n)
				System.out.print(i + " ");
			printt(i*10,n);
			if( i + 1 == 10)
				break;
			++i;
		}
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		printt(1,25);
	}

import math
def sigfig(n, offset):
    return (n / 10 ** (int(math.log(n)/math.log(10))-offset)) % 10

def sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]
    less, more = [], []
    for i in range(len(arr)-1):
        #less, default, more = -1, 0, 1
        state = 0
        n = 0
        while state == 0:
            result = sigfig(pivot, n) - sigfig(arr[i], n)
            if result > 0:
                state = -1
            elif result < 0:
                state = 1
            else:
                if arr[i] < pivot:
                    state = -1
                elif arr[i] > pivot:
                    state = 1
            n += 1
        if state == -1:
            less.append(arr[i])
        else:
            more.append(arr[i])
    return sort(less) + [arr[-1]] + sort(more)
    
print sort([25, 1, 2, 13, 10, 11, 65, 22])

what about this one

using System;

namespace Helloworld
{
    class Program
    {
        static void Main(string[] args)
        {
            
            int N = 250;
            PrintLexicographicRes(1,N);
        }
        public static void PrintLexicographicRes(int i, int N)
        {
            Console.WriteLine(i);
            if(i*10 <= N)
            {
                PrintLexicographicRes(i*10, N);
            }
            int j = i + 1;
            if(j <= N && j%10 != 0)
            {
                PrintLexicographicRes(j, N);
            }
        }
    }
}

Complexity of this is O(N) + O(1).

Here is a simple solution using depth first traversal of this generic tree..

import java.util.*;

public class LexicographicalSort {

     public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        for (int i = 1; i <= 9; i++) {
            dfs(i, n);
        }
    }

    public static void dfs(int i, int n) {
        if (i > n) {
            return;
        }
        System.out.println(i);
        for (int j = 0; j < 10; j++) {
            dfs((i * 10) + j, n);
        }
    }  
}

/* I cheated by using a map and a list. There's probably a more efficient way to do this, but I ain't a genius to figure that sh*t out. */
static void printLexicographicOrder(int n){

	Map<Integer, ArrayList<Integer>> map = new LinkedHashMap<Integer, ArrayList<Integer>>();
	int divisor = 10;
	int key;
	ArrayList<Integer> value;
		
	for(int i = 1; i <= n; i++){

		if( (i / divisor) > 9){
			divisor *= 10;
		}
			
		if( (i % divisor) == i){
			
			key = i; 
			value = new ArrayList<Integer>();
				
		} else {
			key = i / divisor;
			value = map.get(key);
				
		}
			
		value.add(i);
		map.put(key, value);
	}
			
	for(int i = 1; i <= map.size(); i++){
		value = map.get(i);
		for(Integer k: value)
			System.out.println(k);
	}
}