Using Greedy Algorithm to Fix the Broken Calculator
- 时间:2020-09-21 09:15:21
- 分类:网络文摘
- 阅读:89 次
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) —
推荐阅读:Best Video Specs for Facebook 7 Best WordPress Popup Plugins for 2020 How to Optimize Your Content Marketing for SEO The Top Client-Attraction Strategies Side Hustle Tips for the Social Media Savvy A Quick Guide To Creating A User Persona For Your Blog 7 Top Image Compression Plugins For Your WordPress Blog 3 Ways to Convert Blog Readers to Leads 7 Ways To Deal With AdBlock Users If You’re A Blogger 2020 Design Trends [Infographic]
- 评论列表
-
- 添加评论