Iterative and Recursion Algorithms to Compute the Number of Step
- 时间:2020-09-11 08:17:29
- 分类:网络文摘
- 阅读:132 次
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: 6Explanation:
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: 12Constraints:
0 <= num <= 10^6Hints:
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) —
推荐阅读:How to Use Hash Map to Count the Frequencies of Values and Itera Ordered Three 2TB WD HDD to prolong the life expectancy of HPZ80 HPZ800 Server Does Not Support Hard Drives Larger Than 2TB Fresno Blogger Changing The Vegan Blogging Scene Russian ‘Pokemon Go’ Blogger Goes On Trial Starting a Blog? 5 Topics People Care About in 2017 6 Strategies To Grow Your Facebook Page 5 Sure Shot Content Marketing Trends to Follow 7 Ways for Your Underdog Blog to Beat the Competition Darkstore Aims to be Less Invasive Alternative to Tech Giants ac
- 评论列表
-
- 添加评论