Leetcode

Can You Eat Your Favorite Candy on Your Favorite Day?

  • Time:O(n)
  • Space:O(n)

C++

class Solution {
 public:
  vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
    const int n = candiesCount.size();
    vector<bool> ans;
    vector<long> prefix(n + 1);

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

    for (const auto& q : queries) {
      const int type = q[0];
      const int day = q[1];
      const int cap = q[2];
      // min/max day required to eat
      const long minDay = prefix[type] / cap;
      const long maxDay = prefix[type + 1] - 1;
      ans.push_back(minDay <= day && day <= maxDay);
    }

    return ans;
  }
};

JAVA

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];
      // min/max day required to eat
      final long minDay = prefix[type] / cap;
      final long maxDay = prefix[type + 1] - 1;
      ans[i] = minDay <= day && day <= maxDay;
    }

    return ans;
  }
}

Python

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