Skip to content

1103. Distribute Candies to People 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  vector<int> distributeCandies(int candies, long n) {
    vector<int> ans(n);
    int rows = (-n + sqrt(n * n + 8 * n * n * candies)) / (2 * n * n);
    int accumN = rows * (rows - 1) * n / 2;

    for (int i = 0; i < n; ++i)
      ans[i] = accumN + rows * (i + 1);

    int givenCandies = (n * n * rows * rows + n * rows) / 2;
    candies -= givenCandies;

    for (int i = 0, lastGiven = rows * n + 1; candies > 0; ++i, ++lastGiven) {
      int actualGiven = min(lastGiven, candies);
      candies -= actualGiven;
      ans[i] += actualGiven;
    }

    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 int[] distributeCandies(int candies, int num_people) {
    int[] ans = new int[num_people];
    long c = (long) candies;
    long n = (long) num_people;
    int rows = (int) (-n + Math.sqrt(n * n + 8 * n * n * c)) / (int) (2 * n * n);
    int accumN = rows * (rows - 1) * num_people / 2;

    for (int i = 0; i < n; ++i)
      ans[i] = accumN + rows * (i + 1);

    int givenCandies = (num_people * num_people * rows * rows + num_people * rows) / 2;
    candies -= givenCandies;

    for (int i = 0, lastGiven = rows * num_people + 1; candies > 0; ++i, ++lastGiven) {
      int actualGiven = Math.min(lastGiven, candies);
      candies -= actualGiven;
      ans[i] += actualGiven;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def distributeCandies(self, candies: int, n: int) -> list[int]:
    ans = [0] * n
    rows = int((-n + (n**2 + 8 * n**2 * candies)**0.5) / (2 * n**2))
    accumN = rows * (rows - 1) * n // 2

    for i in range(n):
      ans[i] = accumN + rows * (i + 1)

    givenCandies = (n**2 * rows**2 + n * rows) // 2
    candies -= givenCandies
    lastGiven = rows * n
    i = 0

    while candies > 0:
      lastGiven += 1
      actualGiven = min(lastGiven, candies)
      candies -= actualGiven
      ans[i] += actualGiven
      i += 1

    return ans