Katkat
Back

Fewest Add-or-Subtract Power-of-Two Steps to Reduce n to Zero

SalesforceSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

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

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.