15 months ago

Bilal Yasin • 0

Approach

Let dp(i) be a minimum cost to purchase 2 ** i cookies.

We can show that the following holds:

dp(i) = min(dp(i-1) * 2, costs[i])

The final minimum cost would be the minimum of the followings:

- Sum of dp(i), where i is the 1 bit index of M

- Minimnum among dp(k) where 2 ** k >= M

Code

class Solution:
    def birthdayPresent(self, costs: List[int], N: int, M: int) -> int:
        dp = [0] * 32
        dp[0] = costs[0]
        for i in range(1, 32):
            if i < N:
                dp[i] = min(dp[i-1]*2, costs[i])
            else:
                dp[i] = dp[i-1] * 2
        tmp = 0
        ans = math.inf
        for i in range(0, 32):
            if M & (1 << i):
                tmp += dp[i]
            if M <= (1 << i):
                ans = min(ans, dp[i])
        ans = min(ans, tmp)
        return ans

Time & Space Complexity

- Time complexity: O(1)

- Space complexity: O(1)

15 months ago

Puneet Tyagi • 0

Mumbai

can you post other questions