Distribute Candies to People

🏠 ⬅️ ➡️

We distribute some number of candies, to a row of n = num_people people in the following way:

We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n candies to the last person.

Then, we go back to the start of the row, giving n + 1 candies to the first person, n + 2 candies to the second person, and so on until we give 2 * n candies to the last person.

This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies. The last person will receive all of our remaining candies (not necessarily one more than the previous gift).

Return an array (of length num_people and sum candies) that represents the final distribution of candies.

Example 1:

Input: candies = 7, num_people = 4 Output: [1,2,3,1] Explanation: On the first turn, ans[0] += 1, and the array is [1,0,0,0]. On the second turn, ans[1] += 2, and the array is [1,2,0,0]. On the third turn, ans[2] += 3, and the array is [1,2,3,0]. On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

Example 2:

Input: candies = 10, num_people = 3 Output: [5,2,3] Explanation: On the first turn, ans[0] += 1, and the array is [1,0,0]. On the second turn, ans[1] += 2, and the array is [1,2,0]. On the third turn, ans[2] += 3, and the array is [1,2,3]. On the fourth turn, ans[0] += 4, and the final array is [5,2,3].

Constraints:

  • 1 <= candies <= 10^9
  • 1 <= num_people <= 1000
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main

! This program solves the following problem:
! We distribute some number of candies, to a row of n = num_people people in the following way:
! We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n candies to the last person.
! Then, we go back to the start of the row, giving n + 1 candies to the first person, n + 2 candies to the second person, and so on until we give 2 * n candies to the last person.
! This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies. The last person will receive all of our remaining candies (not necessarily one more than the previous gift).
! Return an array (of length num_people and sum candies) that represents the final distribution of candies.

implicit none
integer :: i, j, k, n, m, num_people, candies
integer, dimension(:), allocatable :: ans

! read input
read(*,*) candies, num_people

! allocate memory for the answer array
allocate(ans(num_people))

! initialize the answer array
do i = 1, num_people
    ans(i) = 0
end do

! solve the problem
do while (candies > 0)
    ! give candies to the first person
    if (candies >= 1) then
        ans(1) = ans(1) + 1
        candies = candies - 1
    end if
    
    ! move to the next person
    i = 2
    
    ! give candies to the next person
    do while (candies >= i .and. i <= num_people)
        ans(i) = ans(i) + i
        candies = candies - i
        i = i + 1
    end do
    
    ! move to the start of the row
    i = 1
    
    ! give candies to the next person
    do while (candies >= i .and. i <= num_people)
        ans(i) = ans(i) + i
        candies = candies - i
        i = i + 1
    end do
end do

! print the final distribution of candies
do i = 1, num_people
    write(*,'(I0)',advance='no') ans(i)
end do
write(*,*)

end program main
✅ Compiled
✅ Executed
❌ Correct 
module candy_distribution
implicit none
contains

function distribute_candies(candies, num_people) result(ans)
integer, intent(in) :: candies, num_people
integer :: ans(num_people)
integer :: i, j, k

! Initialize the array with 0s
ans = 0

! Loop through the gifts
do i = 1, num_people
    ! Give out candies
    do j = 1, i
        ans(j) = ans(j) + 1
    end do

    ! Move to the start of the row
    do k = 1, num_people - i
        ans(k) = ans(k) + 1
    end do
end do

! Handle the remaining candies
do j = 1, num_people
    ans(j) = ans(j) + mod(candies, num_people)
end do

end function distribute_candies

end module candy_distribution

program test_candy_distribution
use candy_distribution
implicit none
integer :: candies, num_people, i
integer :: ans(1000)

! Test case 1
candies = 7
num_people = 4
ans = distribute_candies(candies, num_people)
write (*,*) ans

! Test case 2
candies = 10
num_people = 3
ans = distribute_candies(candies, num_people)
write (*,*) ans

! Test case 3
candies = 15
num_people = 5
ans = distribute_candies(candies, num_people)
write (*,*) ans

! Test case 4
candies = 100
num_people = 10
ans = distribute_candies(candies, num_people)
write (*,*) ans

! Test case 5
candies = 1000
num_people = 100
ans = distribute_candies(candies, num_people)
write (*,*) ans

end program test_candy_distribution
🌐 Data from online sources 
def distribute_candies(candies, num_people):
    result = [0] * num_people
    i = 0
    count = 1

    while candies > 0:
        result[i % num_people] += min(candies, count)
        candies -= count
        count += 1
        i += 1

    return result

The algorithm proceeds as follows:
  1. Initialize an array result of length num_people with 0's.
  2. Initialize two variables i and count, both with value 0. i will iterate through the people and count will store how many candies should be given at each step.
  3. Loop until there are no more candies left.
    1. To distribute candies among people:
      • If the remaining candies are more than the current count, give count candies to the current person.
      • If the remaining candies are less than or equal to the current count, give the remaining candies to the current person and stop the loop.
    2. Update the remaining candies by subtracting the current count.
    3. Increment the current count and i.
  4. After the loop, return the result array as the final distribution of candies.
🌐 Data from online sources 
#include <vector>

std::vector<int> distributeCandies(int candies, int num_people) {
    std::vector<int> result(num_people, 0);
    int i = 0, count = 1;

    while (candies > 0) {
        result[i % num_people] += std::min(candies, count);
        candies -= count;
        count++;
        i++;
    }

    return result;
}

The algorithm proceeds as follows:
  1. Initialize an array result of length num_people with 0's.
  2. Initialize two variables i and count, both with value 0. i will iterate through the people and count will store how many candies should be given at each step.
  3. Loop until there are no more candies left.
    1. To distribute candies among people:
      • If the remaining candies are more than the current count, give count candies to the current person.
      • If the remaining candies are less than or equal to the current count, give the remaining candies to the current person and stop the loop.
    2. Update the remaining candies by subtracting the current count.
    3. Increment the current count and i.
  4. After the loop, return the result array as the final distribution of candies.