386. Lexicographical Numbers

Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

Solution:

1. start from curr = 1
   1. if curr * 10 <= n ----> curr * 10 (1->10 transitions)
   2. elif curr + 1 <= n && curr % 10 != 9 (because 9 + 1 will need to change more than one bit, not lexicographical order) --> curr+1 (11 -> 12 transitions)
   3. else
      1. all the numbers ending with 9 are left (499 -> 49, then use the same calculation as ii)
      2. and 13 -> 2 transitions are left (curr -> curr / 10 + 1)

public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<Integer>();
        int curr = 1;
        for(int i = 1; i <= n; i++){
            res.add(curr);
            if(curr * 10 <= n){
                curr *= 10;
            }else if(curr + 1 <= n && curr % 10 != 9){
                curr += 1;
            }else{
                while(curr / 10 % 10 == 9){
                    curr = curr / 10;
                }
                curr = curr / 10 +1;
            }

        }

        return res;
    }

Reference:

https://discuss.leetcode.com/topic/55184/java-o-n-time-o-1-space-iterative-solution-130ms/2