Using Greedy Algorithm to Fix the Broken Calculator
- 时间:2020-09-21 09:15:21
- 分类:网络文摘
- 阅读:156 次
On a broken calculator that has a number showing on its display, we can perform two operations:
- Double: Multiply the number on the display by 2, or;
- Decrement: Subtract 1 from the number on the display.
Initially, the calculator is displaying the number X. Return the minimum number of operations needed to display the number Y.
Example 1:
Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.Example 2:
Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.Example 3:
Input: X = 3, Y = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.Example 4:
Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.Note:
1 <= X <= 10^9
1 <= Y <= 10^9
Greedy Algorithm Fixes the Broken Calculator
A greedy algorithm has a strategy that picks the current optimial solution which will lead to a global optimial solution. But it does not work for all types of problems e.g. Dynamic Programming.
For simplicity, we can look into the problem slightly in a different way. We can transform Y to X, thus only two operations are allows: divided number by two (if it is an even number), and add one to the number.
Dividing by two (if it is an even number) is obviously better (shorter) than do minus, minus, divide, plus, plus. If it is odd number, it seems that we can only increment this number by one.
If Y is smaller than X, then, the greedy approach requires (X – Y) steps. The worst case scenario complexity is O(Max(1, X – Y)).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public: int brokenCalc(int X, int Y) { int ans = 0; while (X < Y) { if (Y % 2 == 0) { Y /= 2; } else { Y ++; } ans ++; } return ans + X - Y; } }; |
class Solution {
public:
int brokenCalc(int X, int Y) {
int ans = 0;
while (X < Y) {
if (Y % 2 == 0) {
Y /= 2;
} else {
Y ++;
}
ans ++;
}
return ans + X - Y;
}
};–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:In-place Run-Length String Compressions using C++ Algorithms to Compute the Factor Combinations for An Integer usi How and Why You Should Use Infographics On Your Blog How to Make Your “Contact Us” Page Kick Ass The A to Z of Content Marketing: Habits Every Content Marketer S Keeping the Flame Going: How to Rock a Steady Job and Still Have How to Use Social Media and User-Generated Content to Boost Traf 7 Types of Blog Posts and When to Use Them How to Maximize Profit From Your Blog Visitors Win a Premium WordPress Theme For Your Blog
- 评论列表
-
- 添加评论