Problem list:

- Divisor Game
- Maximum Difference Between Node and Ancestor
- Longest Arithmetic Sequence
- Recover a Tree From Preorder Traversal

## 1025. Divisor Game

### Problem

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number `N`

on the chalkboard. On each player's turn, that player makes a *move* consisting of:

- Choosing any
`x`

with`0 < x < N`

and`N % x == 0`

. - Replacing the number
`N`

on the chalkboard with`N - x`

.

Also, if a player cannot make a move, they lose the game.

Return `True`

if and only if Alice wins the game, assuming both players play optimally.

**Example 1:**

1 | Input: 2 |

**Example 2:**

1 | Input: 3 |

**Note:**

`1 <= N <= 1000`

https://leetcode.com/contest/weekly-contest-132/problems/divisor-game/

### Solution

The first though was "dynamic programming"...

1 | class Solution { |

Is this an easy one? Yes… Then I found that we just need to check if the given number is even or not.

1 | class Solution { |

Proof:

Firstly, we can prove that the one who gets input `3`

will lose the game.

Consider if `N`

is odd, Alice can only have an odd `x`

, which makes `N-x`

even for Bob. Bob choose whatever an odd number to give another odd number to Alice. Keep going like this, Alice will finally be given a `3`

, she then loses the game.

Consider if `N`

is even, she can play this trick to win the game.

## 1026. Maximum Difference Between Node and Ancestor

### Problem

Given the `root`

of a binary tree, find the maximum value `V`

for which there exists **different** nodes `A`

and `B`

where `V = |A.val - B.val|`

and `A`

is an ancestor of `B`

.

(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)

**Example 1:**

1 | Input: [8,3,10,1,6,null,14,null,null,4,7,13] |

**Note:**

- The number of nodes in the tree is between
`2`

and`5000`

. - Each node will have value between
`0`

and`100000`

.

### Solution

My first try used two nested recursions.

1 | /** |

Actually one depth-first search is enough (by keeping the max and min value):

1 | /** |

## 1027. Longest Arithmetic Sequence

### Problem

Given an array `A`

of integers, return the **length** of the longest arithmetic subsequence in `A`

.

Recall that a *subsequence* of `A`

is a list `A[i_1], A[i_2], ..., A[i_k]`

with `0 <= i_1 < i_2 < ... < i_k <= A.length - 1`

, and that a sequence `B`

is *arithmetic* if `B[i+1] - B[i]`

are all the same value (for `0 <= i < B.length - 1`

).

**Example 1:**

1 | Input: [3,6,9,12] |

**Example 2:**

1 | Input: [9,4,7,2,10] |

**Example 3:**

1 | Input: [20,1,15,3,10,5,8] |

**Note:**

`2 <= A.length <= 2000`

`0 <= A[i] <= 10000`

https://leetcode.com/contest/weekly-contest-132/problems/longest-arithmetic-sequence/

### Solution

The idea is to keep track of two numbers as the first two elements in the sequence using two nested for loop, and then use another for loop interating from the next number to check how many numbers match this sequence:

1 | class Solution { |

## 1028. Recover a Tree From Preorder Traversal

### Problem

We run a preorder depth first search on the `root`

of a binary tree.

At each node in this traversal, we output `D`

dashes (where `D`

is the *depth* of this node), then we output the value of this node. *(If the depth of a node is D, the depth of its immediate child is D+1. The depth of the root node is 0.)*

If a node has only one child, that child is guaranteed to be the left child.

Given the output `S`

of this traversal, recover the tree and return its `root`

.

**Example 1:**

1 | Input: "1-2--3--4-5--6--7" |

**Example 2:**

1 | Input: "1-2--3---4-5--6---7" |

**Example 3:**

1 | Input: "1-401--349---90--88" |

**Note:**

- The number of nodes in the original tree is between
`1`

and`1000`

. - Each node will have a value between
`1`

and`10^9`

.

https://leetcode.com/contest/weekly-contest-132/problems/recover-a-tree-from-preorder-traversal/

### Solution

I didn't attempt to do this one. Found this optimal solution in comments:

1 | /** |