397. Integer Replacement
Problem Description
Given a positive integer n
, the task is to transform this number to 1. There are two types of operations that you are allowed to perform:
- If
n
is even, you can divide it by 2 (n = n / 2
). - If
n
is odd, you can either increase it by 1 (n = n + 1
) or decrease it by 1 (n = n - 1
).
Each operation counts as a single step, and the goal is to find the minimum number of steps required to reduce n
to 1.
Intuition
The intuition behind the solution involves understanding parity (odd or even nature) of n
and using bitwise operations for efficiency. For an even n
, the decision is straightforward: divide by 2. This halving operation is efficient because it significantly reduces n
.
For an odd n
, the decision to subtract or add 1 relies on considering the bits of n
. Specifically, we observe the following patterns:
- When the least significant two bits of
n
are01
(meaning the next division will yield an even number), it is often better to subtract 1 than to add 1, because we want to get to an even number to divide by 2 in the next step. - However, there is a special case when
n
is3
; the best operation is to subtract 1 twice to reach1
rather than add 1 and then divide twice. - If the least significant two bits are
11
, adding 1 convertsn
to an even number, which can then be halved. This is except for the case whenn
is3
, as mentioned above.
The approach makes use of bitwise operations:
- We use
n & 1
to check ifn
is even or odd (0
means even and1
means odd). - The right shift
n >>= 1
effectively dividesn
by 2. - We check if the last two bits are
11
byn & 3
, and if the result is3
, we know adding 1 is a favorable operation.
The solution employs a loop that iteratively applies the optimal operation until n
becomes 1
, and a counter ans
keeps track of the number of operations performed.
Learn more about Greedy, Memoization and Dynamic Programming patterns.
Solution Approach
The solution provided uses a greedy approach to minimize the number of operations needed to reduce n
to 1 with the two allowed operations, substituting and dividing.
Here's a walkthrough of the algorithm using the Reference Solution Approach:
-
Initialize
ans
to 0. This variable will keep track of the total number of operations performed. -
Enter a loop that continues until
n
is equal to 1. -
Inside the loop, check if
n
is even by using the bitwise AND operationn & 1
. If the result is 0, it meansn
is even. -
If
n
is even, we apply the bitwise right shift operationn >>= 1
to n. This operation is equivalent to dividingn
by 2. -
If
n
is odd, we have to decide whether to increment or decrementn
. To make this decision:- Check if
n
is not equal to 3 and if the last two bits ofn
are11
by applying the bitwise AND operationn & 3
. If the result is 3, it's better to incrementn
by 1, because doing so will lead to an even number after this operation. - In all other cases (when
n
is odd, and eithern
is 3 or the last two bits ofn
are not11
), it's better to decrementn
by 1.
- Check if
-
After each operation (incrementing, decrementing, or dividing), increment
ans
by 1 to count the operation. -
Once
n
is reduced to 1, exit the loop, and returnans
as the total number of operations performed.
The solution applies mathematical operations and understands binary representations to guide the decision-making process. No additional data structures are used, and the algorithm runs in a time complexity that is logarithmic to the value of n
, specifically O(log n), because each division by two halves the problem size.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example using n = 15
.
-
Initialize
ans
to 0. At the start, no steps have been taken yet, soans
is0
. -
Because
n
is not 1, we enter the loop. -
As
n
is odd (15 & 1
is1
), we proceed to check if we should decrement or incrementn
. -
Since
n
equals 15, which is not 3, and the last two bits ofn
are11
(15 & 3
gives3
), we incrementn
by 1, resulting inn = 16
. Nowans = 1
. -
Now
n
is even (16 & 1
is0
), so we right shiftn
, effectively dividing it by 2.n
becomes8
(n >>= 1
). Nowans = 2
. -
n
is still even, so we keep right shifting.n
becomes4
. Nowans = 3
. -
Continue with the even case;
n
becomes2
. Nowans = 4
. -
Finally,
n
is2
, which is even again, and after one more shift,n
becomes1
. Nowans = 5
. -
Since
n
is now equal to 1, we break out of the loop. -
The value of
ans
is5
, representing the minimum number of steps needed to transformn
from15
to1
.
The solution successfully applies the steps from the Reference Solution Approach, selecting operations that gradually reduce n
to 1 with optimal efficiency, ending with an answer of 5 steps for this example.
Solution Implementation
1class Solution:
2 def integer_replacement(self, n: int) -> int:
3 # Initialize a counter for the number of steps taken
4 step_count = 0
5
6 # Continue processing until the integer becomes 1
7 while n != 1:
8 # If n is even, shift it right by 1 (equivalent to dividing by 2)
9 if (n & 1) == 0:
10 n >>= 1
11 # If n is one less than a multiple of 4 (except when n is 3)
12 # increment n (e.g., for 7 -> 8 is better than 7 -> 6)
13 elif n != 3 and (n & 3) == 3:
14 n += 1
15 # In all other cases (n is odd and not handled by the above condition), decrement n
16 else:
17 n -= 1
18 # Increment the step count after each operation
19 step_count += 1
20
21 # Return the total number of steps taken
22 return step_count
23
1class Solution {
2 public int integerReplacement(int n) {
3 int steps = 0; // Counter for the number of steps taken to transform 'n' to 1
4
5 while (n != 1) {
6 if ((n & 1) == 0) { // If 'n' is even
7 n >>>= 1; // Right shift (unsigned) to divide 'n' by 2
8 } else if (n != 3 && (n & 3) == 3) { // If 'n' is not 3 and the last two bits are 11
9 n++; // Increment 'n' since it leads to more 0s when it's divided by 2 subsequently
10 } else {
11 n--; // Decrement 'n' if it's odd and doesn't match the previous case
12 }
13 steps++; // Increment the step count after each operation
14 }
15 return steps; // Return the total number of steps once 'n' is reduced to 1
16 }
17}
18
1class Solution {
2public:
3 // Function to determine the minimum number of operations to transform
4 // a given integer n to 1 by either decrementing by 1, incrementing by 1,
5 // or halving it when even.
6 int integerReplacement(int n) {
7 int operationsCount = 0; // variable to count the number of operations
8 long longNumber = n; // use a long to handle overflow
9
10 // Continue until longNumber becomes 1
11 while (longNumber != 1) {
12 if ((longNumber & 1) == 0) {
13 // If longNumber is even, halve it
14 longNumber >>= 1;
15 } else if (longNumber != 3 && (longNumber & 3) == 3) {
16 // If longNumber is not 3 and ends with binary '11', increment it
17 longNumber++;
18 } else {
19 // If longNumber is odd and not covered by the above case, decrement it
20 longNumber--;
21 }
22 // Increment the operation count after each operation
23 operationsCount++;
24 }
25
26 // Return the total count of operations performed
27 return operationsCount;
28 }
29};
30
1// Global variable to count the number of operations
2let operationsCount: number = 0;
3
4// Function to determine the minimum number of operations to transform
5// a given integer n to 1 by either decrementing by 1, incrementing by 1,
6// or halving it when even.
7function integerReplacement(n: number): number {
8 // Initialize count and use a 'BigInt' for 'n' to handle overflow
9 operationsCount = 0;
10 let longNumber: bigint = BigInt(n);
11
12 // Continue processing until longNumber becomes 1
13 while (longNumber !== BigInt(1)) {
14 if ((longNumber & BigInt(1)) === BigInt(0)) {
15 // If longNumber is even, right shift equals dividing by 2
16 longNumber >>= BigInt(1);
17 } else if (longNumber !== BigInt(3) && (longNumber & BigInt(3)) === BigInt(3)) {
18 // If longNumber ends with binary '11' (is odd) and is not 3, increment
19 longNumber++;
20 } else {
21 // If longNumber is odd and not covered by the above case, decrement
22 longNumber--;
23 }
24 // Increment the operation count after each operation
25 operationsCount++;
26 }
27
28 // Return the total count of operations performed
29 return operationsCount;
30}
31
32// Example usage:
33// To call the function, simply invoke it with an integer argument
34// let result: number = integerReplacement(1234);
35
Time and Space Complexity
The given code implements an algorithm to determine the minimum number of operations to reduce a number n
to 1 by either dividing it by 2 if it's even or subtracting 1 or adding 1 if it's odd, which converges to division by 2 when possible.
Time Complexity:
The time complexity of the algorithm is determined by the number of operations needed to reduce n
to 1. In the worst case scenario, for each bit in the binary representation of n
, the loop might be executed twice (once for subtraction/addition to make it even, and once for the division by 2). However, the addition operation in n += 1
can lead to the removal of multiple trailing '1's in binary, which means it's possible to skip several steps at once. Therefore, the time complexity is O(log n)
in the average case, and in the worst case, it's slightly more than O(log n)
due to the possible addition steps that can reduce the number of 1's in the binary representation.
Space Complexity:
The space complexity of the code is O(1)
, as the algorithm uses a fixed amount of space - the variable ans
to keep count of the operations, and n
is modified in place without using additional memory that scales with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Memoization Prereq Backtracking problems backtracking Memoization is a fancy word for a simple concept so is the case for a lot of things we learn in school It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.