CODEWITHSUNDEEP
algorithmmath
Ibrahim Ali
Ibrahim Ali

Reputation: 1297

how to sort the numbers 1, ... n lexicographically without converting the numbers to string?

Assume I have input n how I can print this sequence without convert the number to string?

i.e:-

n = 100 Output :- 1 10 100 11 12 13 14 15 16 17 18 19 2 20 ...

n = 15 Output :- 1 10 11 12 13 14 15 2 3 4 5 6 7 8 9

n = 20 Output :- 1 10 11 12 13 15 15 16 17 18 19 2 20 3 4 5 6 7 8 9

What is the main factor here?

My initial solution that will print the 1's followed by 0's or 2's followed by 0's

 int n = 100;
    for (int i = 1; i <= n; i++) {
        int x = i;
        while (x <= n) {
            System.out.println(x);
            x *= 10;
        }
    }

Upvotes: 4

Views: 117

Answers (2)

coproc
coproc

Reputation: 6257

Here a condensed solution in Python based on the OP's own answer:

def genRangeLexiSorted(n, k=1):
  for i in range(k, min(k+10-k%10, n+1)):
    yield i
    for j in genRangeLexiSorted(n, 10*i):
      yield j

def printnums(n):
  print(*list(genRangeLexiSorted(n)))

Then the calls

printnums(1)
printnums(9)
printnums(11)
printnums(20)
printnums(100)

give the following outputs:

1
1 2 3 4 5 6 7 8 9
1 10 11 2 3 4 5 6 7 8 9
1 10 11 12 13 14 15 16 17 18 19 2 20 3 4 5 6 7 8 9
1 10 100 11 12 13 14 15 16 17 18 19 2 20 21 22 23 24 25 26 27 28 29 3 30 31 32 33 34 35 36 37 38 39 4 40 41 42 43 44 45 46 47 48 49 5 50 51 52 53 54 55 56 57 58 59 6 60 61 62 63 64 65 66 67 68 69 7 70 71 72 73 74 75 76 77 78 79 8 80 81 82 83 84 85 86 87 88 89 9 90 91 92 93 94 95 96 97 98 99

Upvotes: 1

Ibrahim Ali
Ibrahim Ali

Reputation: 1297

I figured out the solution:-

You can call it with initial k = 1 for example printnum(15, 1 

void printnums(int n, int k) {
    if (k > n) {
        return;
    }

    for (int i = 0; i < 10; i++) {
        if (k <= n) {
            System.out.println(k);

            k *= 10;
            printnums(n, k);
            k /= 10;
            k++;
            if (k % 10 == 0) return;
        }
    }
}

I don't know if there are more optimized one?

Upvotes: 3

Related Questions