Can You Eat Your Favorite Candy on Your Favorite Day? - Problem

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.

For each query, determine if you can eat a candy of type favoriteType_i on day favoriteDay_i without eating more than dailyCap_i candies on any day.

Return a boolean array answer where answer[i] is true if you can eat your favorite candy on your favorite day for query i, and false otherwise.

Input & Output

Example 1 — Multiple Query Types

$ Input: candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]

› Output: [true,false,true]

💡 Note: Query 1: Type 0 candy available days 0-6, day 2 ∈ [0,6] ✓. Query 2: Type 4 needs 11 days minimum, but day 2 < 11 ✗. Query 3: Type 2 available days 1-15, day 13 ∈ [1,15] ✓

Example 2 — Single Type Query

$ Input: candiesCount = [5,2,6,4,1], queries = [[3,1,6],[4,10,3],[3,0,1]]

› Output: [false,true,false]

💡 Note: Query 1: Need 7 days minimum for type 3, day 1 too early. Query 2: Type 4 available days 3-17, day 10 ∈ [3,17] ✓. Query 3: Type 3 earliest day 7, day 0 too early

Example 3 — Edge Case Small Array

$ Input: candiesCount = [1], queries = [[0,0,1],[0,1,1]]

› Output: [true,false]

💡 Note: Only 1 candy of type 0. Available only on day 0. First query matches exactly, second query too late

Constraints

1 ≤ candiesCount.length ≤ 10⁵
1 ≤ candiesCount[i] ≤ 10⁵
1 ≤ queries.length ≤ 10⁵
queries[i].length == 3
0 ≤ favoriteType_i < candiesCount.length
0 ≤ favoriteDay_i ≤ 10⁹
1 ≤ dailyCap_i ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 8 f Facebook 6

The key insight is to use prefix sums to quickly calculate the earliest and latest days when each candy type is available. For each query, check if the favorite day falls within this valid range. Best approach is Prefix Sum with Time: O(n + q), Space: O(n).

Common Approaches

✓ Brute Force Simulation

⏱️ Time: O(q × d × c) Space: O(1)

For each query, try all possible daily candy consumption patterns from 1 to dailyCap per day. Check if we can reach the favorite candy type exactly on the favorite day.

Prefix Sum Optimization

⏱️ Time: O(n + q) Space: O(n)

Precompute prefix sums to instantly determine the range of days when each candy type is available. For each query, check if the favorite day falls within the valid range for that candy type.

Brute Force Simulation — Algorithm Steps

For each query, simulate eating candies day by day
Try all combinations of daily consumption (1 to dailyCap)
Check if favorite candy type is available on favorite day

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Range

Calculate earliest and latest days for favorite candy

Validate Day

See if favorite day falls within valid range

Result

Return true if day is reachable, false otherwise

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool* solution(int* candiesCount, int candiesSize, int** queries, int queriesSize, int* returnSize) {
    bool* result = (bool*)malloc(queriesSize * sizeof(bool));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int favoriteType = queries[i][0];
        int favoriteDay = queries[i][1];
        long long dailyCap = queries[i][2];
        
        // Calculate candies before favorite type
        long long candiesBeforeFavorite = 0;
        for (int j = 0; j < favoriteType; j++) {
            candiesBeforeFavorite += candiesCount[j];
        }
        
        // Minimum days to reach favorite type (eating max per day)
        long long minDaysToReachFavorite = (candiesBeforeFavorite + dailyCap - 1) / dailyCap;
        
        // Maximum days to finish favorite type (eating min 1 per day)
        long long candiesUpToFavorite = candiesBeforeFavorite + candiesCount[favoriteType];
        long long maxDaysInFavorite = candiesUpToFavorite - 1;
        
        // Check if favorite day falls within the valid range
        bool possible = (minDaysToReachFavorite <= favoriteDay) && (favoriteDay <= maxDaysInFavorite);
        result[i] = possible;
    }
    
    return result;
}

int parseArray(char* line, int* arr, int maxSize) {
    int count = 0;
    char* ptr = line;
    
    // Skip initial bracket
    while (*ptr && *ptr != '[') ptr++;
    if (*ptr) ptr++;
    
    while (*ptr && count < maxSize) {
        // Skip whitespace and commas
        while (*ptr && (*ptr == ' ' || *ptr == ',' || *ptr == '\t')) ptr++;
        
        if (*ptr == ']' || *ptr == '\0') break;
        
        // Parse number
        char* endptr;
        long val = strtol(ptr, &endptr, 10);
        if (endptr != ptr) {
            arr[count++] = (int)val;
            ptr = endptr;
        } else {
            ptr++;
        }
    }
    
    return count;
}

int parseQueries(char* line, int queries[][3], int maxQueries) {
    int count = 0;
    char* ptr = line;
    
    // Skip initial bracket
    while (*ptr && *ptr != '[') ptr++;
    if (*ptr) ptr++;
    
    while (*ptr && count < maxQueries) {
        // Skip whitespace and commas
        while (*ptr && (*ptr == ' ' || *ptr == ',' || *ptr == '\t')) ptr++;
        
        if (*ptr == ']' || *ptr == '\0') break;
        
        // Look for opening bracket of subarray
        if (*ptr == '[') {
            ptr++;
            // Parse three numbers
            for (int i = 0; i < 3; i++) {
                while (*ptr && (*ptr == ' ' || *ptr == ',' || *ptr == '\t')) ptr++;
                
                char* endptr;
                long val = strtol(ptr, &endptr, 10);
                if (endptr != ptr) {
                    queries[count][i] = (int)val;
                    ptr = endptr;
                } else {
                    return count;
                }
            }
            
            // Skip to closing bracket
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr) ptr++;
            
            count++;
        } else {
            ptr++;
        }
    }
    
    return count;
}

int main() {
    static char line1[10000];
    static char line2[100000];
    static int candiesCount[1000];
    static int queries[1000][3];
    
    // Read candiesCount array
    if (!fgets(line1, sizeof(line1), stdin)) return 1;
    int candiesSize = parseArray(line1, candiesCount, 1000);
    
    // Read queries array
    if (!fgets(line2, sizeof(line2), stdin)) return 1;
    int queriesSize = parseQueries(line2, queries, 1000);
    
    // Convert queries to pointer array
    int* queryPtrs[1000];
    for (int i = 0; i < queriesSize; i++) {
        queryPtrs[i] = queries[i];
    }
    
    int returnSize;
    bool* result = solution(candiesCount, candiesSize, queryPtrs, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf(result[i] ? "true" : "false");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × d × c)

For each query q, simulate up to d days with c possible daily consumptions

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track current state

✓ Linear Space

38.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Can You Eat Your Favorite Candy on Your Favorite Day? - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler