将数字减少到1的最小步骤数

1. Introduction

In this tutorial, we’ll explain reducing a number to one using the minimum number of operations. The operations to use are to add one, subtract one, and divide by two in case the number is even.

We’ll discuss three approaches to solving the problem and see which approaches provide an optimal answer.

2. Defining the Problem

In this problem, we’ll be given a number , and we need to reduce this number to become equal to one using the minimum number of operations.

At each time, we can use one of the following operations:

Add 1 to the current number. Thus, the new number will be .
Subtract 1 from the current number. Therefore, the new number we move to is .
In case $\boldsymbol{N}$ is even, then we can divide it by 2. So, the new number we get is $\frac{N}{2}$ .

For example, if is equal to 28, then the optimal solution is using 6 steps:

$[28 \rightarrow 14 \rightarrow 7 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1]$

Also, if is equal to 13, then the optimal solution is using 5 steps:

$[13 \rightarrow 12 \rightarrow 6 \rightarrow 3 \rightarrow 2 \rightarrow 1]$

3. Non-Optimal Greedy Approach

This greedy approach tries to use the operation that reduces the number as much as possible for the current step. As we know, the number can either be odd or even. If the number is odd, then we can’t use division by 2, and thus we use the operation of subtracting 1.

On the other hand, if the number is even, we can either subtract 1, or divide the number by 2. Since we are following the greedy approach, we choose to divide the number by 2.

For example, if is equal to 10, then the greedy approach will reach 1 after the following 4 steps:

$[10 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1]$

We can prove that this greedy approach doesn’t always provide an optimal solution. A counterexample is if is equal to 15. The greedy approach will give us the following 6 steps:

$[15 \rightarrow 14 \rightarrow 7 \rightarrow 6 \rightarrow 3 \rightarrow 2 \rightarrow 1]$

However, we can find a better solution using only the following 5 steps:

$[15 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1]$

Therefore, we can conclude that this greedy approach is fast, but it doesn’t always give us the optimal solution.

4. BFS Approach

We can find a solution for the problem within the graph theory using the BFS algorithm.

4.1. General Idea

Let’s consider each number to be a node inside the graph. Also, we can consider the edges of the graph to connect the node with nodes N+1 and N-1 . In addition, if is even, then it’ll be connected to N/2 as well.

4.2. Implementation

Let’s take a look at the implementation of this approach:

algorithm BFSApproach(N):
    // INPUT
    //    N = the number to start from
    // OUTPUT
    //    Returns the minimum number of steps to reach number 1

    answer <- an array with 2 * MAX_N elements initialized to infinity
    queue <- an empty set

    answer[N] <- 0
    queue.push(N)

    while not queue.empty():
        N <- queue.top()

        if N = 1:
            break

        queue.pop()

        if N + 1 < 2 * MAX_N and answer[N] + 1 < answer[N + 1]:
            answer[N + 1] <- answer[N] + 1
            queue.push(N + 1)

        if N - 1 > 0 and answer[N] + 1 < answer[N - 1]:
            answer[N - 1] <- answer[N] + 1
            queue.push(N - 1)

        if N mod 2 = 0 and answer[N] + 1 < answer[N / 2]:
            answer[N / 2] <- answer[N] + 1
            queue.push(N / 2)

    return answer[1]

In the beginning, we initialize the array answer with $\infty$ , which will hold the number of steps to get to each number starting from .

Note that the array size should be twice the starting number. The reason is that we may add keep adding 1 to the starting number, but there’s no point in reaching $2 \times MAX \_ N$ because, from that, we can use division by two and go back to . Also, we define a queue for the BFS algorithm.

Then, we set the answer of to zero, since it’s the starting number, and push it into the queue. After that, we keep extracting a number from the queue as long as the queue isn’t empty. For each number, we check whether this number is 1. In this case, we stop the while loop because the algorithm has reached the target number 1.

Otherwise, we check the previously found answer to reach $\boldsymbol{N + 1}$ , $\boldsymbol{N - 1}$ and $\boldsymbol{N / 2}$ . If reaching these numbers from $\boldsymbol{N}$ is better than the way we found before, then we update the $\boldsymbol{answer}$ and push the number into the queue.

Note that we make sure that the new number doesn’t exceed $2 * MAX \_ N$ and doesn’t drop below 1, to respect the size of the answer array. In addition, we only use the operation of division by 2 in case is even.

Finally, we return answer[1] , which contains the minimum number of steps to reach the number 1.

4.3. Complexity

The complexity of the BFS algorithm is O(V+E) , where is the number of vertices and is the number of edges. In this case, the number of vertices is $2 \times N$ , where is the number to start from. On the other hand, each number can connect to 3 numbers in the worst case. Thus, the number of edges is $6 \times N$ .

As a result, the total complexity is $\boldsymbol{O(N)}$ , where is the starting number.

5. Optimal Greedy Approach

We can update the greedy approach in section 3 to obtain a new optimal one.

5.1. Theoretical Idea

Let’s first separate the problem into two cases based on whether is even or odd. If is even, we can prove that the optimal step is to divide the number by 2.

The reason is that we can either use two addition operations and then a division by 2, which will make us reach $\frac{N + 2}{2}$ which is equal to N / 2 + 1 using 3 steps. However, we can reach this number by using 2 steps, which are a division by 2 and then adding 1. Therefore, using a total of 2 operations.

Also, we can use two subtraction operations and then a division by 2. In this case, we’ll reach $\frac{N - 2}{2}$ which is equal to N / 2 - 1 using 3 steps. However, the same number can be obtained by using a division by 2 and then subtracting 1. Thus, using a total of 2 operations only.

In addition, we can eliminate the option of adding and subtracting 1 from , because these two operations negate each other. Therefore, if $\boldsymbol{N}$ is even, then it’s always optimal to divide it by 2.

On the other hand, if is odd, then we need to consider multiple cases. Let’s consider the least 2 significant bits of in case is odd. We have 2 cases x01 and x11 (The represents the rest of the number). We can use the fact that an even number has the optimal choice of dividing by 2 to reach .

In the case of x01 :

If we try to add, we reach . Then, we should go with the division to reach . After that, we can have two options:
- Either add to reach , after which we’ll divide to reach . So, we reach in 4 operations.
- Or, subtract to reach , and then divide to reach . So, we reach in 4 operations.
On the other hand, if we subtracted, we get , after which we’ll make two divisions to reach . As a result, we get the following:
- We can reach by using 3 operations.
- Also, we can perform one more addition to reach in 4 operations.

As a result, we see that subtraction always gives a better or equal answer to adding in the case of numbers that end with $\boldsymbol{01}$ in their binary representation.

The other case is x11 :

If we try to add, then we’ll get . Therefore, we’ll need to divide twice to get . As a result, we get the following cases:
- Reaching requires 3 operations.
- Reaching requires an additional subtraction. So, we can reach after 4 operations.
If we decided to subtract, then we get , after which we should divide to reach . From here, we have two options:
- Adding will make us reach . Then, we divide to get . Therefore, we need 4 operations to get .
- Subtracting will make us reach , after which we’ll divide to reach . Thus, we used 4 operations to get .

As we can see, using the operation of adding 1 is always better in the case of numbers that end with $\boldsymbol{11}$ in their binary representation.

We can conclude this analysis of odd numbers by checking the modular after dividing the number by 4; if it’s a 1 then we decide to subtract. Otherwise, we add 1. The only exception to this is if $\boldsymbol{N}$ is equal to 3, in which case we need to do two subtractions.

5.2. Implementation

Take a look at the implementation of this approach:

algorithm OptimalGreedyApproach(N):
    // INPUT
    //    N = the number to start from
    // OUTPUT
    //    the minimum number of steps to reach number 1

    answer <- 0
    while N > 1:
        if N mod 2 = 0:
            N <- N / 2
        else if N = 3 or N mod 4 = 1:
            N <- N - 1
        else:
            N <- N + 1
        answer <- answer + 1

    return answer

The implementation is similar to the theoretical idea discussed in section 5.1. In case is even, it’s always better to use a division operation. Otherwise, if is either equal to 3, or has a modular of 1 after dividing by 4, then we subtract. In other cases, we use the adding operation.

5.3. Complexity

The complexity of the optimal greedy approach is $\boldsymbol{O(log(N))}$ , where $\boldsymbol{N}$ is the initial number. The reason is that even if we used subtraction or addition, both operations would lead to an even number. Therefore, the division by two operations occurs at least once every two steps.

6. Conclusion

In this article, we discussed reducing a number into 1 by using the operations of either dividing by 2 or adding or subtracting 1.

We discussed three approaches to solve the problem and then explained which approaches give the optimal answer.

Persistence

REST

Security