# LeetCode's Math

Reverse integer, Plus one, Palindrome number

### 1. Given a 64-bit integer, reverse its digits.

Assumption:

```
- Negative numbers are also valid.
- Must handle the case where the reversed integer is overflow.
```

Example:

```
- Input: 123
Output: 321
- Input: -123
Output: -321
- Input: 8085774586302733229 Output: 0
Explanation: The reversed integer 9223372036854775808 overflows by 1 so we return 0.
```

Approach:

```
- Use modulo by 10 to get a digit at ones' place of the input and
dividing by 10 to shift it to the right (eliminate the ones' place).
```

Cost:

```
- O(m) time, O(1) space, where m is log10 of the input.
```

### 2. Given a number represented as an array of digits, plus one to the number.

Assumption:

```
- The input are non-negative.
- The digits are stored such that the most significant digit is at the head of the list.
- The number does not contain leading zeros.
```

Example:

```
- Input: []int{1, 2, 5}
Output: []int{1, 2, 6}
- Input: []int{1, 2, 9}
Output: []int{1, 3, 0}
- Input: []int{1, 9, 9}
Output: []int{2, 0, 0}
```

Approach:

```
- Iterate through the list from right to left and add 1 to the current digit accordingly.
- If the current digit is less than 9, add 1 and update it.
- Otherwise, set it to 0.
- If all the digits are 9, append an 0 in the end and update the first digit to 1.
```

Cost:

```
- O(n) time, O(1) space, where n is the length of the list.
```

### 3. Determine whether an integer is a palindrome.

Assumption:

```
- Do this without extra space.
- Define negative integers as non-palindrome.
```

Example:

```
- Input: 101
Output: true
- Input: 106
Output: false
```

Approach:

```
- Use two-pointer approach where one starts at the first digit and one starts
at the last digit, have them walk toward the middle and compare them at each
step.
```

Cost:

```
- O(n) time, O(1) space.
```

For more coding problems, please visit https://github.com/hoanhan101/algo.

Tagged: #leetcode, #algorithm