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 N, 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:

  1. Add 1 to the current number. Thus, the new number will be N + 1.
  2. Subtract 1 from the current number. Therefore, the new number we move to is N - 1.
  3. 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 N 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 N 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 N 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 N 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 N with nodes N+1 and N-1. In addition, if N 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:

Rendered by QuickLaTeX.com

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

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 N. Also, we define a queue for the BFS algorithm.

Then, we set the answer of N to zero, since it’s the starting number, and push it into the queue. After that, we keep extracting a number N 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 N 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 V is the number of vertices and E is the number of edges. In this case, the number of vertices is 2 \times N, where N 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 N 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 N is even or odd. If N 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 N, 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 N is odd, then we need to consider multiple cases. Let’s consider the least 2 significant bits of N in case N is odd. We have 2 cases x01 and x11 (The x represents the rest of the number). We can use the fact that an even number x0 has the optimal choice of dividing by 2 to reach x.

In the case of x01:

  1. If we try to add, we reach x10. Then, we should go with the division to reach x1. After that, we can have two options:
    • Either add to reach (x + 1)0, after which we’ll divide to reach x + 1. So, we reach x + 1 in 4 operations.
    • Or, subtract to reach x0, and then divide to reach x. So, we reach x in 4 operations.
  2. On the other hand, if we subtracted, we get x00, after which we’ll make two divisions to reach x. As a result, we get the following:
    • We can reach x by using 3 operations.
    • Also, we can perform one more addition to reach x + 1 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:

  1. If we try to add, then we’ll get (x + 1)00. Therefore, we’ll need to divide twice to get x + 1. As a result, we get the following cases:
    • Reaching x + 1 requires 3 operations.
    • Reaching x requires an additional subtraction. So, we can reach x after 4 operations.
  2. If we decided to subtract, then we get x10, after which we should divide to reach x1. From here, we have two options:
    • Adding will make us reach (x + 1)0. Then, we divide to get x + 1. Therefore, we need 4 operations to get x + 1.
    • Subtracting will make us reach x0, after which we’ll divide to reach x. Thus, we used 4 operations to get x.

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:

Rendered by QuickLaTeX.com

The implementation is similar to the theoretical idea discussed in section 5.1. In case N is even, it’s always better to use a division operation. Otherwise, if N 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 N 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.

Comments are open for 30 days after publishing a post. For any issues past this date, use the Contact form on the site.