Fewest Terms to Write an Integer as 1, 2 or 3 Plus Even Powers of Two
Company: Visa
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
You are given an integer array `nums`. For each value `x` in `nums`, find the smallest positive integer `k` such that `x` can be written as the sum of exactly `k` integers where:
- exactly one of the `k` integers is `1`, `2` or `3`, and
- each of the other `k - 1` integers is a power of two whose exponent is even and at least `2`, that is, one of `4`, `16`, `64`, `256`, `1024`, and so on. The power `2^0 = 1` is not allowed for these terms.
If no such `k` exists for `x`, the answer for `x` is `-1`. Return the answers as a list in the same order as `nums`.
### Function Signature
```python
def min_split_terms(nums: list[int]) -> list[int]:
```
### Rules
- The same power of two may appear any number of times among the `k - 1` terms.
- `k = 1` is allowed. The sum then consists of the single small term, so this applies only when `x` itself is `1`, `2` or `3`.
- The order of the terms does not matter; only the count `k` is returned.
- Every value in `nums` is answered independently of the others.
### Constraints
- `1 <= len(nums) <= 100000`
- `1 <= nums[i] <= 1000000000`
- The output has the same length as `nums`. Each element is `-1` or a positive integer, and it is uniquely determined by the input.
### Examples
**Example 1**
- Input: `nums = [1, 5, 4, 23, 14]`
- Output: `[1, 2, -1, 3, 4]`
- Explanation: `1` is itself a small term, so `k = 1`. `5 = 1 + 4`. For `4`, the small term would be `1`, `2` or `3`, leaving `3`, `2` or `1` for the other terms, and none of those can be a sum of terms that are each at least `4`, so the answer is `-1`. `23 = 3 + 4 + 16`. `14 = 2 + 4 + 4 + 4`, and no choice with fewer terms reaches `14`.
**Example 2**
- Input: `nums = [3, 63]`
- Output: `[1, 7]`
- Explanation: `3` is a small term on its own. `63 = 3 + 16 + 16 + 16 + 4 + 4 + 4`, and no choice with fewer than seven terms reaches `63`.
Overview: For every integer in an array, find the fewest terms that sum to it when exactly one term is 1, 2 or 3 and every other term is a power of two with an even exponent, such as 4, 16 or 64, or return -1 when this is impossible. It tests number-theoretic reasoning about divisibility and minimal representations under large input sizes.
Read the full Visa Software Engineer interview experience this question came from
You are given an integer array `nums`. For each value `x` in `nums`, find the smallest positive integer `k` such that `x` can be written as the sum of exactly `k` integers where:
- exactly one of the `k` integers is `1`, `2` or `3` (the *small term*), and
- each of the other `k - 1` integers is a power of two whose exponent is even and at least `2`, that is, one of `4`, `16`, `64`, `256`, `1024`, and so on. The power `2^0 = 1` is not allowed for these terms.
If no such `k` exists for `x`, the answer for `x` is `-1`. Return the answers as a list in the same order as `nums`.
**Rules**
- The same power of two may appear any number of times among the `k - 1` terms.
- `k = 1` is allowed. The sum then consists of the single small term, so this applies only when `x` itself is `1`, `2` or `3`.
- The order of the terms does not matter; only the count `k` is returned.
- Every value in `nums` is answered independently of the others.
**Output**
Return a list with the same length as `nums`, where the element at index `i` is the answer for `nums[i]`. Each element is `-1` or a positive integer and is uniquely determined by the input. All inputs and answers fit in a signed 32-bit integer.
**Example 1**
Input: `nums = [1, 5, 4, 23, 14]`
Output: `[1, 2, -1, 3, 4]`
`1` is itself a small term, so `k = 1`. `5 = 1 + 4`. For `4`, the small term would be `1`, `2` or `3`, leaving `3`, `2` or `1` for the other terms, and none of those can be a sum of terms that are each at least `4`, so the answer is `-1`. `23 = 3 + 4 + 16`. `14 = 2 + 4 + 4 + 4`, and no choice with fewer terms reaches `14`.
**Example 2**
Input: `nums = [3, 63]`
Output: `[1, 7]`
`3` is a small term on its own. `63 = 3 + 16 + 16 + 16 + 4 + 4 + 4`, and no choice with fewer than seven terms reaches `63`.
**Constraints**
- `1 <= len(nums) <= 100000`
- `1 <= nums[i] <= 1000000000`
Constraints
- 1 <= len(nums) <= 100000
- 1 <= nums[i] <= 1000000000
- Each answer is -1 or a positive integer; all values fit in a signed 32-bit integer
Examples
Input: ([1, 5, 4, 23, 14],)
Expected Output: [1, 2, -1, 3, 4]
Input: ([3, 63],)
Expected Output: [1, 7]
Hints
- Every term other than the small one is a multiple of 4. What does that force about the small term, given x?
- Once the small term is fixed, divide the rest by 4: you need the fewest powers of 4 (now including 1) that sum to a given number.
- Four copies of the same power of 4 can always be merged into the next power. What representation does that leave you with?