Make Two Apple Piles Equal With Doubling Moves
Company: Optiver
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You have two piles of apples: the first pile contains `a` apples and the second pile contains `b` apples.
In one move you choose one pile to be the **receiving** pile and move apples into it from the other pile. The number of apples moved must be exactly the number of apples the receiving pile currently contains, so the receiving pile doubles in size. A move is legal only if the giving pile holds at least that many apples.
Determine whether there is a finite sequence of moves after which both piles contain the same number of apples. Return `true` if it is possible (including when the piles are already equal), and `false` otherwise.
**Function signature**
```
canBalance(a, b) -> boolean
```
**Input**
- `a` — the number of apples in the first pile
- `b` — the number of apples in the second pile
**Output**
- `true` if the two piles can be made equal through some sequence of legal moves, `false` otherwise.
**Constraints**
- `1 <= a, b <= 10^9`
- The answer must be produced efficiently for values up to the full constraint range.
**Examples**
1. `a = 3, b = 5` → `true`
Move 3 apples from the second pile onto the first: `(3, 5) → (6, 2)`. Then move 2 apples from the first pile onto the second: `(6, 2) → (4, 4)`. The piles are equal.
2. `a = 1, b = 2` → `false`
The reachable states cycle: `(1, 2) → (2, 1) → (1, 2) → ...` — the piles never become equal.
3. `a = 2, b = 4` → `false`
`(2, 4) → (4, 2) → (2, 4) → ...` — the states repeat and equality is never reached.
4. `a = 7, b = 7` → `true`
The piles are already equal; zero moves are needed.
Quick Answer: This question evaluates algorithmic problem-solving and discrete-mathematics competencies, focusing on reasoning about state transitions, invariants, and number-theoretic constraints within the Coding & Algorithms domain for data scientist roles.
You have two piles of apples: the first pile contains `a` apples and the second pile contains `b` apples.
In one move you choose one pile to be the **receiving** pile and move apples into it from the other pile. The number of apples moved must be exactly the number of apples the receiving pile currently contains, so the receiving pile **doubles** in size. A move is legal only if the giving pile holds at least that many apples.
Determine whether there is a finite sequence of moves after which both piles contain the same number of apples. Return `true` if it is possible (including when the piles are already equal), and `false` otherwise.
**Function signature**
```
solution(a, b) -> boolean
```
**Input**
- `a` — the number of apples in the first pile
- `b` — the number of apples in the second pile
**Output**
- `true` if the two piles can be made equal through some sequence of legal moves, `false` otherwise.
**Examples**
1. `a = 3, b = 5` → `true`. `(3,5) → (6,2) → (4,4)`.
2. `a = 1, b = 2` → `false`. States cycle `(1,2) → (2,1) → (1,2) …`.
3. `a = 2, b = 4` → `false`. States cycle and never balance.
4. `a = 7, b = 7` → `true`. Already equal; zero moves.
**Key idea.** The total `S = a + b` is invariant, so the target is `S/2` in each pile, which requires `S` even. Tracking one pile value `x`, every legal move sends `x → 2x (mod S)` and the choice is forced, so the reachable states form a single deterministic path. Writing `S = 2^s · q` with `q` odd, the state `S/2` is reachable from `a` iff `v2(a) < s` **and** `q` divides `a` (where `v2` is the exponent of 2 dividing `a`). This runs in O(log S), well within the 10^9 constraint.
Constraints
- 1 <= a, b <= 10^9
- The answer must be computed efficiently for values up to the full range (no per-step simulation up to 10^9).
Examples
Input: (3, 5)
Expected Output: True
Explanation: S=8=2^3, q=1. v2(3)=0<3 and 1|3. Concretely (3,5)->(6,2)->(4,4).
Input: (1, 2)
Expected Output: False
Explanation: S=3 is odd, so S/2 is not an integer; the piles can never be equal.
Input: (2, 4)
Expected Output: False
Explanation: S=6=2*3, s=1, so v2(2)=1 is not < 1. The path 2->4->2->... never hits S/2=3.
Input: (7, 7)
Expected Output: True
Explanation: Already equal; zero moves. S=14, v2(7)=0<1 and q=7 divides 7.
Input: (1, 1)
Expected Output: True
Explanation: Already equal. S=2=2^1, v2(1)=0<1, q=1 divides 1.
Input: (1, 5)
Expected Output: False
Explanation: S=6=2*3, q=3 does not divide a=1, so unreachable.
Input: (3, 9)
Expected Output: True
Explanation: S=12=2^2*3, s=2, q=3|3, v2(3)=0<2. (3,9)->(6,6).
Input: (1000000000, 1000000000)
Expected Output: True
Explanation: Full-range already-equal case; handled in O(log S).
Hints
- The total number of apples a + b never changes. For the piles to end equal, a + b must be even and each pile must reach (a + b)/2.
- Track just one pile value x (the other is S - x). Because a move is only legal in one direction depending on which pile is larger, each move deterministically sends x -> 2x (mod S). So the reachable states are a single forced path.
- Write S = 2^s * q with q odd. The target S/2 has 2-adic valuation s-1. Analyzing 2^k * a (mod S) via CRT shows S/2 is reachable iff v2(a) < s AND q divides a.