Lexicographical Numbers

https://leetcode.com/problems/lexicographical-numbers/discuss/

class Solution {
    List<Integer> res;
    public List<Integer> lexicalOrder(int n) {
        res = new ArrayList<>();
        for(int i = 1; i < 10; i++){
            helper(i, n);
        }

        return res;
    }

    private void helper(int cur, int n){
        if(cur > n){
            return;
        }

        res.add(cur);
        for(int i = 0; i < 10; i++){
            if(cur * 10 + i <= n){
                helper(cur * 10 + i, n);
            }
        }
    }
}

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

K-th Smallest in Lexicographical Order

https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/discuss/

public int findKthNumber(int n, int k) {
    int curr = 1;
    k = k - 1;
    while (k > 0) {
        int steps = calSteps(n, curr, curr + 1);
        if (steps <= k) {
            curr += 1;
            k -= steps;
        } else {
            curr *= 10;
            k -= 1;
        }
    }
    return curr;
}
//use long in case of overflow
public int calSteps(int n, long n1, long n2) {
    int steps = 0;
    while (n1 <= n) {
        steps += Math.min(n + 1, n2) - n1;
        n1 *= 10;
        n2 *= 10;
    }
    return steps;
}