Fewest Add-or-Subtract Power-of-Two Steps to Reduce n to Zero
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
You are given a positive integer `n`. In one operation you may add `2**i` to the current value or subtract `2**i` from it, for any integer `i >= 0` you choose; each operation may use a different `i`.
Return the minimum number of operations needed to turn `n` into `0`.
### Function Signature
```python
def min_power_of_two_steps(n: int) -> int:
```
### Rules
- The same power of two may be used in more than one operation.
- Intermediate values are unrestricted: they may exceed `n` or drop below `0`. Only the final value must be exactly `0`.
- Only the number of operations is returned, not the sequence.
### Constraints
- `1 <= n <= 9007199254740991` (that is, `2**53 - 1`). The original assessment allowed `n` up to `2**60 - 1`; this version caps `n` so that every supported language represents it exactly.
- `n` can exceed `2**31 - 1`, so use 64-bit or arbitrary-precision integers.
- The result is a positive integer, and it is uniquely determined by `n`.
### Examples
**Example 1**
- Input: `n = 7`
- Output: `2`
- Explanation: Add `1` to reach `8`, then subtract `8` to reach `0`. One operation is not enough, because `7` is not a power of two.
**Example 2**
- Input: `n = 45`
- Output: `4`
- Explanation: One optimal sequence subtracts `32`, `8`, `4` and `1`. No sequence of three operations works.
**Example 3**
- Input: `n = 1000`
- Output: `3`
- Explanation: Add `16` and then `8` to reach `1024`, then subtract `1024`. No sequence of two operations works.
Overview: An integer problem: reduce a positive n to zero with the fewest operations, where each operation adds or subtracts a power of two. It tests reasoning about binary representations, proving a strategy optimal, and working safely with integers larger than 32 bits.