Skip to content

1744. Can You Eat Your Favorite Candy on Your Favorite Day? 👎

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
    const int n = candiesCount.size();
    vector<bool> ans;
    vector<long> prefix{0};

    for (int i = 0; i < n; ++i)
      prefix.push_back(prefix.back() + candiesCount[i]);

    for (const vector<int>& query : queries) {
      const int type = query[0];
      const int day = query[1];
      const int cap = query[2];
      // the minimum day required to eat
      const long minDay = prefix[type] / cap;
      // the maximum day required to eat
      const long maxDay = prefix[type + 1] - 1;
      ans.push_back(minDay <= day && day <= maxDay);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public boolean[] canEat(int[] candiesCount, int[][] queries) {
    final int n = candiesCount.length;
    boolean[] ans = new boolean[queries.length];
    long[] prefix = new long[n + 1];

    for (int i = 0; i < n; ++i)
      prefix[i + 1] = prefix[i] + candiesCount[i];

    for (int i = 0; i < queries.length; ++i) {
      final int type = queries[i][0];
      final long day = (long) queries[i][1];
      final long cap = (long) queries[i][2];
      // the minimum day required to eat
      final long minDay = prefix[type] / cap;
      // the maximum day required to eat
      final long maxDay = prefix[type + 1] - 1;
      ans[i] = minDay <= day && day <= maxDay;
    }

    return ans;
  }
}

1
2
3
4
class Solution:
  def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
    prefix = [0] + list(itertools.accumulate(candiesCount))
    return [prefix[t] // c <= d < prefix[t + 1] for t, d, c in queries]