# Week 4: Recursion

### 1) Power of Three

Given an integer `n`

, return `true`

if it is a power of three. Otherwise, return `false`

.

An integer `n`

is a power of three, if there exists an integer `x`

such that `n == 3^x`

.

**Example 1:**

```
Input: n = 27
Output: true
Explanation: 27 = 3^3
```

**Example 2:**

```
Input: n = 0
Output: false
Explanation: There is no x where 3^x = 0.
```

**Example 3:**

```
Input: n = -1
Output: false
Explanation: There is no x where 3^x = (-1).
```

*Constraints:*

`-2^31 <= n <= 2^31 - 1`

### 2) Remove Nodes From Linked List

You are given the `head`

of a linked list.

Remove every node which has a node with a greater value anywhere to the right side of it.

Return the `head`

of the modified linked list.

**Example 1:**

```
Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.
- Node 13 is to the right of node 5.
- Node 13 is to the right of node 2.
- Node 8 is to the right of node 3.
```

**Example 2:**

```
Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.
```

*Constraints:*

- The number of the nodes in the given list is in the range
`[1, 10^5]`

. `1 <= Node.val <= 10^5`

### 3) Tower of Hanoi

A peg contains rings in sorted order, with the largest ring being the lowest. There are three pegs, the `initial`

peg, the `destination`

peg, and a `buffer`

peg. The `destination`

and `buffer`

pegs start off empty, and the `initial`

peg has n rings on it. Transfer these rings to the `destination`

peg.

The only operation you can perform is taking a single ring from the top of one peg and placing it on top of another peg. You cannot place a larger ring above a smaller one. Write a function which, given `n`

(the number of rings on the initial peg), return the number of steps it would take to move all the rings from the initial peg to the destination peg.

**Example:**

```
Input: n = 3
Output: 7
0th to 1st -> 0th to 2nd -> 1st to 2nd -> 0th to 1st -> 2nd to 0th -> 2nd to 1st -> 0th to 1st
```

### 4) Cherry Trees

An early frost has caused extensive damage to a cherry orchard. The orchard consists of rows of trees where each row can be represented by a string of characters, i.e., `.......`

(seven dots) represents a row of seven (undamaged) trees. Two of the workers have taken it upon themselves to assess the damage to the trees.

The first worker reports the positions and conditions of all the trees in a row, but they are not sure about the conditions of some of the trees. Their list reports trees as undamaged (`.`

), damaged (`#`

), or unknown (`?`

). For the row of seven trees, the worker reports the string `???.###`

, where the conditions of first three trees are unknown, the fourth tree is undamaged, and the last three trees are damaged.

The other worker reports contiguous groups of damaged trees in a row. Their list always accounts for every damaged tree, and each number is the entire size of its contiguous group (that is, groups are always separated by at least one undamaged tree: `####`

would always be `4`

, never `2,2`

). For the same row of seven trees, this worker reports the list `[1, 1, 3]`

, meaning there are three groups of damaged trees of size one, one, and three (in that order).

Find the number of possible combinations of damaged/undamaged trees that satisfy both workersâ€™ reports.

**Example 1:**

```
Input: positions = '???.###' groups = [1, 1, 3]
Output: 1
Explanation: There is exactly one way separate groups of one, one, and three damaged trees (in that order) can
appear in that row: the first three unknown trees must be damaged, then undamaged, then damaged (#.#), making
the whole row #.#.###.
```

**Example 2:**

```
Input: positions = '.??..??...?##.' groups = [1, 1, 3]
Output: 4
Explanation: The last '?' must always be damaged (to satisfy the final contiguous group of three damaged trees),
and each '??' must hide exactly one of the two damaged trees. Neither '??' could be both damaged or they would
form a single contiguous group of two damaged trees. Since each '??' can either be '#.' or '.#', there are four
possible arrangements of trees.
```

**Example 3:**

```
Input: positions = '?###????????' groups = [3, 2, 1]
Output: 10
Explanation: Because the first number is 3, the first and second '?' must both be '.' (if either were '#', the
first number would have to be 4 or higher). However, the remaining run of unknown tree conditions have many
different ways they could hold groups of two and one damaged trees:
.###.##.#...
.###.##..#..
.###.##...#.
.###.##....#
.###..##.#..
.###..##..#.
.###..##...#
.###...##.#.
.###...##..#
.###....##.#
```