Math

Add Two Numbers

See https://notes.jinjunliu.com/8_leetcode/8.4_linked_list/#add-two-numbers

Reverse Integer

Link: https://leetcode.com/problems/reverse-integer/

Code:

class Solution {
    public int reverse(int x) {
        int rev = 0, pop;
        while (x != 0) {
            pop = x % 10;
            x = x / 10;
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

• Time Complexity: {{< katex >}}O(\log(x)){{< /katex >}}. There are roughly {{< katex >}}\log_{10}(x){{< /katex >}} digits in x.

• Space Complexity: O(1).

• If rev * 10 + pop cause overflow, then it must be that rev >= Integer.MAX_VALUE / 10;

• If rev > Integer.MAX_VALUE / 10, then it is guaranteed to overflow.

• If rev = Integer.MAX_VALUE, then it will overflow if and only if pop > 7, because 2^31 - 1 = 2147483647 = Integer.MAX_VALUE.

• Similar logic applies to Integer.MIN_VALUE. Integer.MIN_VALUE is represented as -2^31 = -2147483648.

Palindrome Number

Link: https://leetcode.com/problems/palindrome-number/

Code:

Solution 1: stack and queue

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) return false;
        Stack<Integer> stack = new Stack<>();
        Queue<Integer> queue = new LinkedList<>();
        int pop;
        while (x != 0) {
            pop = x % 10;
            x = x / 10;
            stack.push(pop);
            queue.add(pop);
        }
        while (!stack.isEmpty()) {
            if (stack.pop() != queue.poll()) return false;
        }
        return true;
    }
}

• Note that Queue is an abstract class in Java, so we need to use LinkedList to implement it.

• Stack methods: push, pop, peek, isEmpty. Refer to https://www.geeksforgeeks.org/stack-class-in-java/ for more details.

• Queue methods: add, poll, peek, isEmpty. Refer to https://www.geeksforgeeks.org/queue-interface-java/ for more details.

Solution 2: reverse half of the integer and compare

class Solution {
    public boolean isPalindrome(int x) {
        // when x < 0, x is not palindrome;
        // if last digit is 0, x must be 0 to be a palindrome;
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int revertedNumber = 0;
        
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x = x / 10;
        }
        // when the length is a odd number, we can get rid of the middle digit by revertedNumber / 10
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

• we only revert half of the int number;

• when the original number is less than the reversed number, it means we've processed half of the number digits.