Scale Engineer

Take Gifts From the Richest Pile

Easy
#2338Time: O(k * n log n), where `n` is the number of piles and `k` is the number of seconds. In each of the `k` iterations, we sort the array, which takes O(n log n) time. This makes it the slowest approach.Space: O(log n) to O(n). The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a dual-pivot Quicksort, which requires O(log n) space on average but can degrade to O(n) in the worst case.1 company
Data structures
ArrayHeap (Priority Queue)
Companies
DE Shaw

Prompt

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.
  • Reduce the number of gifts in the pile to the floor of the square root of the original number of gifts in the pile.

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process by sorting the array in each of the k seconds. Sorting makes it easy to find the maximum element, which is always the last element in the sorted array. However, re-sorting the entire array k times is computationally expensive and inefficient.

Algorithm

  • Repeat the process k times.
  • In each iteration, sort the entire gifts array in ascending order.
  • The largest element will be at the end of the sorted array (gifts[n-1]).
  • Replace this largest element with the floor of its square root.
  • After k iterations, calculate the sum of all elements in the modified array and return it.

Walkthrough

The most straightforward, yet least efficient, way to solve this problem is to follow the instructions literally but use sorting to simplify finding the maximum value. In each of the k seconds, we sort the gifts array. The pile with the maximum number of gifts will then be the last element. We update this pile's value to the floor of its square root. We repeat this process k times. Finally, we sum up the remaining gifts in the array.

import java.util.Arrays; class Solution {    public long pickGifts(int[] gifts, int k) {        int n = gifts.length;        for (int i = 0; i < k; i++) {            // Sort the array to find the max element easily            Arrays.sort(gifts);                        // The last element is the maximum            int maxGifts = gifts[n - 1];                        // Take the gifts and update the pile            gifts[n - 1] = (int) Math.floor(Math.sqrt(maxGifts));        }                // Calculate the sum of remaining gifts        long totalGifts = 0;        for (int gift : gifts) {            totalGifts += gift;        }                return totalGifts;    }}

Complexity

Time

O(k * n log n), where `n` is the number of piles and `k` is the number of seconds. In each of the `k` iterations, we sort the array, which takes O(n log n) time. This makes it the slowest approach.

Space

O(log n) to O(n). The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a dual-pivot Quicksort, which requires O(log n) space on average but can degrade to O(n) in the worst case.

Trade-offs

Pros

  • Simple to conceptualize as it directly uses a standard library function (sort) to find the maximum.

Cons

  • Extremely inefficient due to the high cost of sorting the entire array in every single iteration.

  • The time complexity is significantly worse than other possible solutions.

Solutions

class Solution {public  long pickGifts(int[] gifts, int k) {    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->b - a);    for (int v : gifts) {      pq.offer(v);    }    while (k-- > 0) {      pq.offer((int)Math.sqrt(pq.poll()));    }    long ans = 0;    for (int v : pq) {      ans += v;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem