Halve the Total with the Fewest Exact Reductions
Company: Nutanix
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
The entries of `nums` begin as positive integers. In one operation, replace any current entry by exactly half of its value, retaining fractional parts. You may choose the same entry again in later operations. Return the minimum number of operations needed to decrease the total by at least half of its original value.
```cpp
class Solution {
public:
int halveArray(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
nums = [8,2]
Output: 2
Explanation: Halving 8 twice removes 4+2=6, at least half the initial sum 10; one operation removes at most 4.
```
**Example 2:**
```text
nums = [4,4]
Output: 2
Explanation: One halving removes 2, below the target 4; halving both entries reaches it.
```
### Constraints
- `1 <= nums.length <= 10^5`.
- `1 <= nums[i] <= 10^7`.
### Clarifying Questions
Halving is exact, without rounding down. The threshold is inclusive and is based on the original sum.
```hint Inspect the structure
For each entry, how do its available future reductions change after repeated halvings?
```
### Reasoning checkpoints
- Use exact halving rather than rounding down, including repeated operations on one entry.
- Prove that the operation count is minimal and apply the inclusive half-total threshold.
- Explain how the implementation's numeric representation remains reliable under the supplied bounds.
### Optional extensions
How could you justify a numeric representation that avoids rounding uncertainty under these bounds?
Overview: Halve the Total with the Fewest Exact Reductions. Starting from positive integer entries nums, one operation replaces any current entry by exactly half its value, including fractional values. You may repeatedly choose an already reduced entry. Return the fewest operations that reduce the original sum by at least half.
