Iterative and Recursion Algorithms to Compute the Number of Step

  • Time:2020-09-11 08:17:29
  • Class:Weblog
  • Read:31

Given a non-negative integer num, return the number of steps to reduce it to zero. If the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Example 1:
Input: num = 14
Output: 6

Explanation:
Step 1) 14 is even; divide by 2 and obtain 7.
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3.
Step 4) 3 is odd; subtract 1 and obtain 2.
Step 5) 2 is even; divide by 2 and obtain 1.
Step 6) 1 is odd; subtract 1 and obtain 0.
Example 2:

Input: num = 8
Output: 4
Explanation:
Step 1) 8 is even; divide by 2 and obtain 4.
Step 2) 4 is even; divide by 2 and obtain 2.
Step 3) 2 is even; divide by 2 and obtain 1.
Step 4) 1 is odd; subtract 1 and obtain 0.
Example 3:

Input: num = 123
Output: 12

Constraints:
0 <= num <= 10^6

Hints:
Simulate the process to get the final answer.

Iterative Approach

We can simulate the process until we make the number zero (simple, intuitive and effective).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numberOfSteps (int num) {
        int r = 0;
        while (num != 0) {
            r ++;
            if (num % 2 == 0) {
                num >>= 1;
            } else {
                num --;
            }
        }
        return r;
    }
};
class Solution {
public:
    int numberOfSteps (int num) {
        int r = 0;
        while (num != 0) {
            r ++;
            if (num % 2 == 0) {
                num >>= 1;
            } else {
                num --;
            }
        }
        return r;
    }
};

Recursive Algorithm

Alternatively, we can do this recursively but this approach is at the risk of stack-overflow.

1
2
3
4
5
6
7
class Solution {
public:
    int numberOfSteps (int num) {
        return num == 0 ? 0 : 1 + 
                numberOfSteps(num % 2 == 0 ? num / 2 : num - 1);
    }
};
class Solution {
public:
    int numberOfSteps (int num) {
        return num == 0 ? 0 : 1 + 
                numberOfSteps(num % 2 == 0 ? num / 2 : num - 1);
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

Recommend:
5 Tips for Protecting Your Freelance Business from Liabilities
5 Easy Ways On How To Build An Authority Website
How to Protect Your WordPress Site From Hackers
Top 10 Relationship Blogs With the Best Pieces of Advice in 2020
How to Construct Binary Search Tree from Preorder Traversal in P
Dynamic Programming Algorithm to Compute the Block Sum in a Matr
Smallest Multiple Algorithm using Bruteforce or GCD/LCM
How many different ways can £2 be made using any number of coins
Compute Factorial Digit Sum: Find the sum of the digits in the n
Compute the Maximum Integer Right Triangles Solutions
Share:Facebook Twitter
Comment list
Comment add