We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Can You Eat Your Favorite Candy on Your Favorite Day?

Difficulty: Medium

Problem Description

You are given a (0-indexed) array of positive integers candiesCount where candiesCount[i] represents the number of candies of the i-th type you have. You are also given a 2D array queries where queries[i] = [favoriteType_i, favoriteDay_i, dailyCap_i].

You play a game with the following rules:

  • You start eating candies on day 0.
  • You cannot eat any candy of type i unless you have eaten all candies of type i - 1.
  • You must eat at least one candy per day until you have eaten all the candies.

Construct a boolean array answer such that answer.length == queries.length and answer[i] is true if you can eat a candy of type favoriteType_i on day favoriteDay_i without eating more than dailyCap_i candies on any day, and false otherwise. Note that you can eat different types of candy on the same day, provided that you follow rule 2.

Return the constructed array answer.

Key Insights

  • You can only eat candies of type i after finishing all candies of type i-1.
  • Each day, you must eat at least one candy and cannot exceed the daily cap.
  • The total number of candies consumed affects how many days it takes to reach a specific type of candy.
  • A prefix sum can be utilized to calculate the total candies eaten up to a given type.

Space and Time Complexity

Time Complexity: O(n + q), where n is the number of candy types and q is the number of queries.
Space Complexity: O(1), as we are using a constant amount of extra space.

Solution

To solve the problem, we will:

  1. Calculate the prefix sums of the candiesCount array to determine the total number of candies available up to each type.
  2. For each query, check:
    • The total amount of candies needed to reach the favoriteType.
    • The number of days required to reach the favoriteDay.
    • Ensure that the daily cap is not exceeded on any day.
  3. Return a boolean array indicating the result for each query.

We will utilize an array to store the cumulative sum of candies and use it to evaluate each query efficiently.

Code Solutions

def canEat(candiesCount, queries):
    n = len(candiesCount)
    prefix_sum = [0] * n
    prefix_sum[0] = candiesCount[0]
    
    for i in range(1, n):
        prefix_sum[i] = prefix_sum[i - 1] + candiesCount[i]
    
    answer = []
    
    for favoriteType, favoriteDay, dailyCap in queries:
        total_candies_required = prefix_sum[favoriteType]
        days_needed = (total_candies_required - 1) // dailyCap + 1
        
        if favoriteDay < days_needed:
            answer.append(False)
        else:
            max_candies_eaten_by_favorite_day = favoriteDay * dailyCap + dailyCap
            if max_candies_eaten_by_favorite_day >= total_candies_required:
                answer.append(True)
            else:
                answer.append(False)
    
    return answer
← Back to All Questions