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.