Coding questions · Visa

Fewest Terms to Write an Integer as 1, 2 or 3 Plus Even Powers of Two

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.

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

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.

One Small Part Plus Powers of Four

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?

Approach

All of the k - 1 large terms are powers of 4 that are at least 4, so their sum is divisible by 4. The small term s is therefore forced: s must equal x mod 4. If x is a multiple of 4, no s in {1, 2, 3} works and the answer is -1. Otherwise the remaining amount x - s is 4 * m, and we need the fewest powers of 4 (4^0 allowed after dividing by 4) that sum to m. Whenever a representation uses the same power four or more times, replacing four copies by one copy of the next power lowers the count by 3, so an optimal representation uses each power at most three times; that is exactly the base-4 representation of m, which is unique. The minimum is therefore the sum of the base-4 digits of m, and k = 1 + that digit sum. The reference computes this for each element independently by repeatedly taking m % 4 and dividing by 4.

Time complexity: O(n log_4 V), where n = len(nums) and V = max(nums[i])
Space complexity: O(1) extra besides the O(n) output list