Split Powers to Hit a Total
Every item of nums is a power of two (1, 2, 4, 8, ...). One split takes away an item larger than 1 and puts two items of half its value in its place.
Return the fewest splits after which some of the items add up to exactly target, or -1 if that can never happen.
Example 1
nums [2,16]
target 6
returns 2
Split 16 into 8 and 8, then one 8 into 4 and 4. Now 2 + 4 = 6.
Example 2
nums [1,1]
target 3
returns -1
The items only add up to 2.
Example 3
nums [4,1]
target 5
returns 0
4 + 1 is 5 already.
Constraints
1 <= len(nums) <= 200nums[i]is a power of two from 1 to2**301 <= target < 2**31
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Bits problems
- Build a MaskBeginner
- Fixed Width BinaryBeginner
- Flip One BitBeginner
- Gray Code SequenceBeginner
- How Many Bits LongBeginner
- Keep the Low BitsBeginner
- Lowest Set BitBeginner
- Parity BitBeginner