#397

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Integer Replacement

Find the minimum number of operations to reduce a number to 1 by applying specific operations, using state transition dynamic programming.

dynamic programming greedy bit manipulation memoization

Problem Statement

Given a positive integer n, your task is to reduce n to 1 by applying the following operations: if n is even, divide it by 2; if n is odd, either subtract 1 or add 1. You need to return the minimum number of operations needed to achieve this goal.

For example, starting from n = 8, the sequence would be 8 -> 4 -> 2 -> 1, requiring 3 operations. However, different values of n may require different sequences and operations. The problem can be solved using state transition dynamic programming, taking advantage of bit manipulation when applicable.

Examples

Example 1

Input: n = 8

Output: 3

8 -> 4 -> 2 -> 1

Example 2

Input: n = 7

Output: 4

7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1

Example 3

Input: n = 4

Output: 2

Example details omitted.

Constraints

1 <= n <= 231 - 1

Solution Approach

State Transition Dynamic Programming

The problem can be approached by maintaining a state transition for each number and calculating the minimum steps required for each state. We explore both dividing by 2 and subtracting 1 (or adding 1 for odd numbers) to build a dynamic programming table that captures the minimum steps for each intermediate number.

Bit Manipulation Optimization

For even numbers, division by 2 is optimal, but for odd numbers, we can either subtract 1 or add 1. Using bit manipulation, odd numbers can be quickly checked and processed by evaluating their least significant bit, which allows faster decision-making on whether to add or subtract.

Greedy Approach with Memoization

A greedy strategy can be applied to prioritize operations that reduce the number as quickly as possible. Memoization can be used to store results of previously calculated states, ensuring that redundant calculations are avoided and the solution is optimized.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final approach used. If dynamic programming or a recursive solution with memoization is applied, the time complexity is O(log n) due to the nature of halving the number. The space complexity can also vary, but it typically remains O(log n) for storing intermediate results during computation.

What Interviewers Usually Probe

Understand dynamic programming and state transitions.
Identify efficient ways to optimize the problem using bit manipulation.
Evaluate the trade-offs between greedy approaches and memoization.

Common Pitfalls or Variants

Common pitfalls

Not considering the optimal approach for odd numbers (subtract or add 1).
Failing to memoize results, which can lead to redundant computations and inefficient solutions.
Missing edge cases like n = 1 or n being a large number close to 231 - 1.

Follow-up variants

Extend the problem to handle non-positive integers.
Limit the number of operations or add constraints on the maximum allowed steps.
Explore a version where you must also track the exact sequence of operations taken.

FAQ

What is the key strategy to solve the Integer Replacement problem?

The Integer Replacement problem can be solved effectively using state transition dynamic programming, combined with bit manipulation for faster decision-making on odd numbers.

How does memoization help in solving Integer Replacement?

Memoization helps by storing the results of intermediate steps, ensuring that you avoid recalculating the minimum steps for the same number multiple times.

What is the time complexity of the optimal solution for Integer Replacement?

The optimal solution typically has a time complexity of O(log n) due to the nature of halving the number in each step.

How do you handle odd numbers in Integer Replacement?

For odd numbers, you can either subtract 1 or add 1, and bit manipulation can help in making this decision efficiently based on the least significant bit.

Can Integer Replacement be solved with a greedy approach?

Yes, a greedy approach can be used to prioritize operations that reduce the number quickly, although memoization may be necessary for optimal performance.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def integerReplacement(self, n: int) -> int:
        ans = 0
        while n != 1:
            if (n & 1) == 0:
                n >>= 1
            elif n != 3 and (n & 3) == 3:
                n += 1
            else:
                n -= 1
            ans += 1
        return ans

Continue Practicing

#464 can i win #638 shopping offers #691 stickers to spell word