Minimize steps to reduce integer
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given a positive integer n (1 <= n <= 2^61 -
1), in one step you may replace n with n/2 if n is even, or with n+1 or n-1 if n is odd. Return the minimum number of steps to reduce n to 1. Explain your algorithm, justify how you decide between n+1 and n-1 for odd n, and analyze time complexity.
Quick Answer: This question evaluates algorithm design skills and proficiency with integer operations and decision-making under parity constraints, testing competencies such as bitwise reasoning, greedy and dynamic-programming intuition, and complexity analysis.