Skip to content

1815. Maximum Number of Groups Getting Fresh Donuts 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
 public:
  int maxHappyGroups(int batchSize, vector<int>& groups) {
    int happy = 0;
    vector<int> freq(batchSize);

    for (int g : groups) {
      g %= batchSize;
      if (g == 0) {
        ++happy;
      } else if (freq[batchSize - g]) {
        --freq[batchSize - g];
        ++happy;
      } else {
        ++freq[g];
      }
    }

    return happy + dp(freq, 0, batchSize);
  }

 private:
  map<vector<int>, int> memo;

  // Max # of partitions you can form given
  // Current freq and current remainder r
  int dp(const vector<int>& freq, int r, const int& batchSize) {
    if (const auto it = memo.find(freq); it != memo.cend())
      return it->second;

    int ans = 0;

    if (any_of(freq.begin(), freq.end(), [](int f) { return f != 0; })) {
      for (int i = 0; i < freq.size(); ++i)
        if (freq[i]) {
          vector<int> newFreq(freq);
          --newFreq[i];
          ans = max(ans, dp(newFreq, (r + i) % batchSize, batchSize));
        }
      if (r == 0)
        ++ans;
    }

    return memo[freq] = ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
  public int maxHappyGroups(int batchSize, int[] groups) {
    int happy = 0;
    int[] freq = new int[batchSize];

    for (int g : groups) {
      g %= batchSize;
      if (g == 0) {
        ++happy;
      } else if (freq[batchSize - g] > 0) {
        --freq[batchSize - g];
        ++happy;
      } else {
        ++freq[g];
      }
    }

    return happy + dp(freq, 0, batchSize);
  }

  private Map<String, Integer> memo = new HashMap<>();

  private int dp(int[] freq, int r, int batchSize) {
    final String hashed = hash(freq);
    if (memo.containsKey(hashed))
      return memo.get(hashed);

    int ans = 0;

    if (Arrays.stream(freq).anyMatch(f -> f != 0)) {
      for (int i = 0; i < freq.length; ++i)
        if (freq[i] > 0) {
          int[] newFreq = freq.clone();
          --newFreq[i];
          ans = Math.max(ans, dp(newFreq, (r + i) % batchSize, batchSize));
        }
      if (r == 0)
        ++ans;
    }

    memo.put(hash(freq), ans);
    return ans;
  }

  private String hash(int[] freq) {
    StringBuilder sb = new StringBuilder();
    for (final int f : freq)
      sb.append("#").append(f);
    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
    happy = 0
    freq = [0] * batchSize

    for g in groups:
      g %= batchSize
      if g == 0:
        happy += 1
      elif freq[batchSize - g]:
        freq[batchSize - g] -= 1
        happy += 1
      else:
        freq[g] += 1

    @functools.lru_cache(None)
    def dp(freq, r):
      ans = 0
      if any(freq):
        for i, f in enumerate(freq):
          if f:
            ans = max(ans, dp(freq[:i] + (f - 1,) +
                              freq[i + 1:], (r + i) % batchSize))
        if r == 0:
          ans += 1
      return ans

    return happy + dp(tuple(freq), 0)