Maximum Value After Repeated Doubling
You are given an array of integers and an integer $n$. Repeatedly perform the following operation: if the current value of $n$ appears somewhere in the array, double $n$; then check again. Stop as soon as the current value of $n$ is no longer present in the array. Return the final value of $n$.
Constraints:
- \leq \text{len(arr)} \leq 10^{5}$
- values fit in a 64-bit integer
Examples:
- Input: $\text{arr} = [1, 2, 4, 5]$, $n = 1$ -> Output: $8$ (1 present -> 2; 2 present -> 4; 4 present -> 8; 8 absent, stop)
- Input: $\text{arr} = [3, 6, 7]$, $n = 5$ -> Output: $5$ (5 absent immediately)
Hints
- The value only ever doubles, so how many times can it possibly stay inside the array's value range?
- Use a hash set so each 'is the current value present?' check is $O(1)$.
- Loop: while $n$ is in the set, replace $n$ with
Worked Solution
How to Think About It: The operation only ever doubles $n$, so the sequence of values you test is $n, 2n, 4n, 8n, \ldots$ -- it grows geometrically and can repeat at most $O(\log(\max))$ times before exceeding the largest array value. Put the array into a hash set for $O(1)$ membership, then keep doubling while the current value is in the set.
Algorithm: Build a set from the array. While $n$ is in the set, set $n \leftarrow 2n$. Return $n$.
Code:
```python def max_after_doubling(arr, n): present = set(arr) while n in present: n *= 2 return n ```
Complexity: $O(\text{len(arr)})$ to build the set, then at most $O(\log V)$ doublings where $V$ is the largest value. Space $O(\text{len(arr)})$.
Answer: Hash the array, then double $n$ while it stays in the set; terminates in $O(\log V)$ steps because each step at least doubles $n$.
Intuition
The whole problem hinges on recognizing that geometric growth self-limits: doubling can only happen a logarithmic number of times before the value escapes any bounded set, so there is no risk of an infinite loop and no need for cycle detection. This is a tiny example of a broader habit -- before writing a while loop, prove it terminates and bound its iterations. The hashing step is the standard membership-test optimization that turns an $O(n)$ scan per check into $O(1)$.