Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
LeetCode 200 simple questions
Topic describes
Xiao Kou plans to use plug-ins for his OWN VS Code installation. In the initial state, the bandwidth can complete 1 plug-in download per minute. Assume one of the following two strategies is selected per minute:
- Download the plug-in using the current bandwidth
- Double the bandwidth (double the number of plug-ins downloaded)
Please return to the button to complete the n plug-in download the minimum number of minutes.
Note: The actual number of plug-ins downloaded can exceed N
Example 1:
Input: n = 2 Output: 2
Explanation:
Both of the following solutions can download 2 plug-ins in 2 minutes
Plan 1: double the bandwidth in the first minute and download 2 plug-ins per minute; Second minute download 2 plugins
Plan 2: Download 1 plug-in in the first minute and 1 plug-in in the second minute
Example 2:
Enter: n = 4
Output: 3
Explanation: It takes at least 3 minutes to download 4 plug-ins. Here is one of the solutions: double the bandwidth in the first minute and download 2 plug-ins per minute; Second minute download 2 plugins; Minute 3 Download 2 plugins.
prompt
1 <= n <= 10^5
Their thinking
After reading the title for three times, I didn’t see what it meant. Then I tested it by myself, and the result was 4. To recap the subject, take n = 8 as an example:
- The bandwidth doubles in the first minute, currently 2 at a time,
- The bandwidth doubles in the second minute. Currently, it can play 4 at a time.
- The bandwidth is doubled in the third minute, currently 8 at a time,
- Minutes 4 Download 8 plugins.
The key to solve the problem is that before you can finish a download, double all the time until the number of downloads >= N, so that the time is the shortest, the idea is clear, the code is very simple to achieve.
def leastMinutes(self, n) :
""" :type n: int :rtype: int """
res = 0
while 2**res < n:
res += 1
return res + 1
Copy the code
Clocking is completed today, and the current progress is 2/200.