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

Quick Overview

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.

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

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

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 ```python 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.

Overview: 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 either 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`. 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. The minimum is uniquely determined by `n`, so there is exactly one correct output for every input. 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. 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 (long in Java, long long in C++). Intermediate values such as n + 1 can reach 2^53, which still fits in a signed 64-bit integer and is represented exactly by a JavaScript number. - The result is a positive integer (at most 27 for this range of n), returned as a plain integer.

Constraints

1 <= n <= 9007199254740991 (2^53 - 1); the original assessment allowed n up to 2^60 - 1, and this version caps n so every supported language represents it exactly
n can exceed 2^31 - 1: use 64-bit integers (long in Java, long long in C++) or arbitrary precision
Each operation adds or subtracts 2^i for any integer i >= 0; powers may repeat and intermediate values are unrestricted
Return the minimum operation count, a positive integer uniquely determined by n

Examples

Input: (7,)

Expected Output: 2

Input: (45,)

Expected Output: 4

Hints

Look at n in binary. What does adding 1 do to a block of consecutive trailing ones?
Process bits from least significant to most significant. When the lowest set bit is isolated, removing it directly is never worse; when it starts a run of two or more ones, a carry can replace the whole run.
After handling the lowest bit, the value is even, so you can shift right and repeat. The whole algorithm takes one pass over the bits.

Approach

Think of the answer as writing n as a sum of signed powers of two with as few terms as possible. Scan n from its lowest bit. If the lowest bit is 0, there is nothing to do at this position, so shift right. If the lowest bit is 1, some operation must use 2^0 at this level (after shifting), so one operation is spent. When the two lowest bits are 01, the set bit is isolated and subtracting it leaves a clean zero bit. When they are 11, the bit is the start of a run of ones; adding 1 turns the entire run into zeros and pushes a single carry upward, so a run of length k >= 2 costs 2 operations (one add, one subtract at the top) instead of k. This greedy produces the non-adjacent form of n, the signed-binary representation in which no two adjacent digits are nonzero, and that representation is known to have the minimum number of nonzero digits; each nonzero digit is exactly one operation. For example, 45 (binary 101101) is rewritten as 64 - 16 - 4 + 1, which is four operations. Because n < 2^53, the loop runs at most 54 times, and the largest intermediate value is 2^53, which fits in a signed 64-bit integer (JavaScript uses BigInt internally to keep the bit operations exact).

Time complexity:

O(log n)

Space complexity:

O(1)