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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Can You Eat Your Favorite Candy on Your Favorite Day?

Number: 1872

Difficulty: Medium

Paid? No

Companies: Fleetx

Problem Description

Given an array candiesCount where candiesCount[i] represents the number of candies of type i, and a list of queries where each query is of the form [favoriteType, favoriteDay, dailyCap]. You must determine for each query if it’s possible to eat a candy of type favoriteType exactly on favoriteDay under these rules:

  • You start eating candies on day 0.
  • You cannot eat any candy of type i unless you have finished all candies of type i - 1.
  • You must eat at least one candy per day until all candies are finished. Also, you are restricted by not eating more than dailyCap candies on any day. Return a boolean array indicating if it's possible to have a candy of favoriteType eaten on favoriteDay.

Key Insights

  • Use a prefix sum array over candiesCount to quickly determine the total candies consumed before a given candy type.
  • For each query, determine the minimum and maximum candies that can be eaten by favoriteDay given the daily eating restrictions.
  • Check if the range of possible candies consumed overlaps with the range in which the favoriteType candies are eaten.
  • The valid conditions are:
    • The minimum candies eaten (day+1, since you eat at least one per day) should be no more than the total candies up to favoriteType.
    • The maximum candies eaten ( (day+1) * dailyCap ) must be greater than the total candies before favoriteType.

Space and Time Complexity

Time Complexity: O(n + q) where n is the length of candiesCount and q is the number of queries. Space Complexity: O(n) for storing the prefix sum array (ignoring the output array).

Solution

First, build a prefix sum array from candiesCount to compute cumulative totals. For each query, define:

  • minCandiesEaten = favoriteDay + 1 (if you eat one candy every day)
  • maxCandiesEaten = (favoriteDay + 1) * dailyCap (if you eat the maximum allowed candies every day)
  • prevCandies = (if favoriteType is 0 then 0 else prefix[favoriteType - 1])
  • currentTotal = prefix[favoriteType] (total candies up to and including the favorite type)

The query is satisfied if and only if:

  1. minCandiesEaten <= currentTotal
  2. maxCandiesEaten > prevCandies

These conditions ensure that there is an intersection between the range of possible total candies eaten by the favorite day and the set of candies that contains favoriteType.

Code Solutions

# Python solution with detailed comments

def canEat(candiesCount, queries):
    n = len(candiesCount)
    prefix = [0] * n
    prefix[0] = candiesCount[0]
    # Build prefix sum array where prefix[i] is the total candies from type 0 to i
    for i in range(1, n):
        prefix[i] = prefix[i-1] + candiesCount[i]
        
    results = []
    # Process each query
    for favoriteType, favoriteDay, dailyCap in queries:
        # Minimal candies eaten by day favoriteDay if eating at least one candy each day
        minCandiesEaten = favoriteDay + 1
        # Maximum candies eaten by day favoriteDay if eating the maximum allowed candies each day
        maxCandiesEaten = (favoriteDay + 1) * dailyCap
        
        # Total candies before favoriteType
        prevCandies = 0 if favoriteType == 0 else prefix[favoriteType - 1]
        # Total candies to include the entire favoriteType
        currentTotal = prefix[favoriteType]
        
        # Check for intersection between [minCandiesEaten, maxCandiesEaten] and (prevCandies, currentTotal]
        if minCandiesEaten <= currentTotal and maxCandiesEaten > prevCandies:
            results.append(True)
        else:
            results.append(False)
    
    return results

# Example usage:
candiesCount = [7,4,5,3,8]
queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
print(canEat(candiesCount, queries))  # Output: [True, False, True]
← Back to All Questions