Take Gifts From the Richest Pile

🏠 ⬅️ ➡️

You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:

  • Choose the pile with the maximum number of gifts.
  • If there is more than one pile with the maximum number of gifts, choose any.
  • Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.

Return the number of gifts remaining after k seconds.

Example 1:

Input: gifts = [25,64,9,4,100], k = 4 Output: 29 Explanation: The gifts are taken in the following way: - In the first second, the last pile is chosen and 10 gifts are left behind. - Then the second pile is chosen and 8 gifts are left behind. - After that the first pile is chosen and 5 gifts are left behind. - Finally, the last pile is chosen again and 3 gifts are left behind. The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.

Example 2:

Input: gifts = [1,1,1,1], k = 4 Output: 4 Explanation: In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile. That is, you can't take any pile with you. So, the total gifts remaining are 4.

Constraints:

  • 1 <= gifts.length <= 103
  • 1 <= gifts[i] <= 109
  • 1 <= k <= 103
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 5
    integer, dimension(n) :: gifts
    integer :: k
    integer :: i

    gifts = [25, 64, 9, 4, 100]
    k = 4
    call solve(gifts, k)

    gifts = [1, 1, 1, 1]
    k = 4
    call solve(gifts, k)

contains

subroutine solve(gifts, k)
    implicit none
    integer, intent(inout) :: gifts(:)
    integer, intent(in) :: k
    integer :: max_gifts
    integer :: i

    do i = 1, k
        max_gifts = maxval(gifts)
        where (gifts == max_gifts)
            gifts = gifts - floor(sqrt(real(max_gifts)))
        end where
    end do

    print '(I0)', sum(gifts)
end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module gifts
  implicit none
contains
  function solve(gifts, k) result(remaining)
    integer, intent(in) :: gifts(:), k
    integer :: remaining
    integer :: i, j, max_gifts, num_gifts

    remaining = 0
    do i = 1, k
      ! Find the maximum number of gifts in any pile
      max_gifts = 0
      do j = 1, size(gifts)
        if (gifts(j) > max_gifts) then
          max_gifts = gifts(j)
        end if
      end do

      ! Leave behind the floor of the square root of the maximum number of gifts
      num_gifts = int(sqrt(real(max_gifts)))
      remaining = remaining + max_gifts - num_gifts

      ! Take the rest of the gifts
      gifts = gifts - num_gifts
    end do
  end function solve
end module gifts

program test
  use gifts
  implicit none
  integer, parameter :: k = 4
  integer, parameter :: gifts(5) = [25, 64, 9, 4, 100]
  integer :: remaining

  remaining = solve(gifts, k)
  write (*,*) 'Remaining gifts:', remaining
end program test
🌐 Data from online sources 
import math

def giftsRemaining(gifts, k):
    for i in range(k):
        gifts.sort()
        max_index = len(gifts) - 1
        gifts[max_index] -= int(math.sqrt(gifts[max_index]))
    return sum(gifts)

The algorithm iterates k times, in each iteration: 1. Sort the array gifts in non-decreasing order. 2. Find the maximum number of gifts in the pile (last element after sorting). 3. Update the maximum pile by removing the taken gifts from it, which is the number of gifts minus the floor of its square root. 4. After the k iterations, calculate the sum of the elements in the gifts array and return it.

🌐 Data from online sources 
#include <vector>
#include <algorithm>
#include <cmath>

int giftsRemaining(std::vector<int>& gifts, int k) {
    for (int i = 0; i < k; i++) {
        std::sort(gifts.begin(), gifts.end());
        int maxIndex = gifts.size() - 1;
        gifts[maxIndex] -= (int)(sqrt(gifts[maxIndex]));
    }
    int remaining_gifts = 0;
    for (int gift : gifts) remaining_gifts += gift;
    return remaining_gifts;
}

The algorithm iterates k times, in each iteration: 1. Sort the array gifts in non-decreasing order. 2. Find the maximum number of gifts in the pile (last element after sorting). 3. Update the maximum pile by removing the taken gifts from it, which is the number of gifts minus the floor of its square root. 4. After the k iterations, calculate the sum of the elements in the gifts array and return it.