Untitled

mail@pastecode.io avatar
unknown
java
3 years ago
3.1 kB
2
Indexable
Never
public class Test {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        solve2(n);
    }

    // non-recursive/simple loop
    private static void solve(int n) {
        int curr = 1;
        do {
            System.out.println(curr);
        } while ((curr = next2(curr, n)) != -1);
    }

    private static boolean next(LinkedList<Character> curr, int n) {
        // try appending '0'--this will always be the successor lexicographically but may not be smaller than 'n'
        curr.addLast('0');
        if (toInteger(curr) <= n) {
            return true;
        } else {
            curr.removeLast();
        }

        // try and increment the last digit without going over 'n'
        while (true) {
            if (curr.isEmpty()) {
                return false;
            }

            char lastDigit = curr.removeLast();
            if (lastDigit == '9') {
                continue;
            } else {
                curr.addLast(++lastDigit);
                if (toInteger(curr) <= n) {
                    return true;
                }
            }
        }
    }

    // TODO: this is too slow to be used in next()
    private static int toInteger(LinkedList<Character> curr) {
        String asString = curr.stream()
                .collect(StringBuilder::new, StringBuilder::append, StringBuilder::append)
                .toString();
        return Integer.parseInt(asString);
    }

    // same as next() but does not waste time converting between string and int
    private static int next2(int curr, int n) {
        // not necessary because n is bounded to a small int, but whatever)
        curr = Math.multiplyExact(curr, 10);
        if (curr <= n) {
            return curr;
        } else {
            curr /= 10;
        }

        while (true) {
            if (curr <= 0) {
                return -1;
            }

            int lastDigit = curr % 10;
            if (lastDigit == 9) {
                curr /= 10;
                continue;
            } else {
                curr++;
                if (curr <= n) {
                    return curr;
                }
            }
        }
    }

    // if we visualize the above algorithm, it's basically doing a dfs of a trie where the first level has nodes
    // '1', '2', ... and then below that, every node has 10 children '0', '1', etc (the 'while' loop where it
    // ends up chopping off the tail of 'curr' is basically it going back up the tree). So let's just write that dfs
    private static void solve2(int n) {
        for (int firstDigit = 1; firstDigit <= 9; firstDigit++) {
            dfs(firstDigit, n);
        }
    }

    private static void dfs(int curr, int n) {
        if (curr > n) {
            // base case
            return;
        } else {
            System.out.println(curr);
            for (int appendDigit = 0; appendDigit <= 9; appendDigit++) {
                dfs((curr * 10) + appendDigit, n);
            }
        }
    }
}