Practice Two Sigma Coding Question | Real Coding Interviews

Quick Summary

Find the minimum number of steps to reduce a positive integer to zero.
Each move consists of adding or subtracting any power of two.
The value may temporarily drop below zero during the process.

What This Tests

Bit manipulation and binary representation analysis
Greedy algorithm design and local vs global optimality
Mathematical pattern recognition and edge case handling
Time complexity optimization for large numerical inputs

Common Patterns

Greedy

Bit Manipulation

(This question is a variation of the LeetCode question 397. Integer Replacement . If you haven't completed that question yet, it is recommended to solve it first.)

You are given a positive integer n. Your task is to reduce this number to zero using as few steps as possible.

Test Cases

Input

Output

Expected