How should I practice Minimum Operations to Reduce an Integer to Zero?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Minimum Operations to Reduce an Integer to Zero associated with Microsoft?

FastPrep tags this as a Microsoft online assessment coding practice problem when the problem catalog has that company and stage context.

Minimum Operations to Reduce an Integer to Zero

Microsoft● MediumFULLTIMEOA

Learn

Problem statement

Given a positive integer n, return the minimum number of operations needed to reduce it to zero.

In one operation, you may add or subtract 2^b for any nonnegative integer b. Intermediate values may be larger than the starting value. Count only these additions and subtractions; rewriting a number in binary is not an operation.

Function

minOperations(n: int) → int

Examples

Example 1

n = 39return = 3

One optimal sequence is 39 - 32 = 7, 7 + 1 = 8, then 8 - 8 = 0, using 3 operations.

Example 2

n = 54return = 3

Use 54 + 2 = 56, 56 + 8 = 64, then 64 - 64 = 0.

Example 3

n = 8return = 1

Subtract 2^3 = 8 once.

Constraints

For this exercise, assume 1 <= n <= 10^5.
Each operation adds or subtracts one power of two.