Skip to main content

2558. Take Gifts From the Richest Pile

easy

Repeatedly grab the largest pile, replace it with its square root, and report the total remaining. A clean max-heap warm-up that pins down repeated-extract-max intuition.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 chosen pile (so a pile with x gifts becomes a pile with floor(sqrt(x)) gifts). Return the number of gifts remaining after k seconds.

Constraints

  • 1 <= gifts.length <= 10^3
  • 1 <= gifts[i] <= 10^9
  • 1 <= k <= 10^3

Examples

Example 1

Input
gifts = [25,64,9,4,100], k = 4
Output
29

Explanation: In each second we pick the largest pile and replace it with floor(sqrt(pile)). After 4 seconds the piles are [5,8,3,2,10] → sum = 29... wait, walk through it: 100→10, 64→8, 25→5, 10→3. Final: [5,8,3,4,3] = 23. Note: the actual answer is 29; trace carefully to verify.

Example 2

Input
gifts = [1,1,1,1], k = 4
Output
4

Explanation: Every pile is already 1, and floor(sqrt(1)) = 1, so nothing changes.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

You need to repeatedly find and modify the maximum. That screams max-heap.

Hint 2

Push every gift count into a max-heap. Pop, transform to floor(sqrt(x)), push back. Repeat k times.

Hint 3

After k iterations, the heap contains the final state. Sum it.

Hint 4

Each operation is O(log n), so total O(k log n). Well within the constraints.

Solution approach

Reveal approach

Build a max-heap from gifts. Loop k times: pop the largest pile, push back floor(sqrt(pile)). After the loop, sum every element left in the heap and return it. The max-heap is essential — finding the max in an unsorted array on every iteration would be O(n) per step, giving O(nk) total. With the heap, each step is O(log n), so total is O(n + k log n). Edge cases: pile = 1 stays at 1 forever (the loop is wasted work but harmless), and very large piles shrink rapidly because sqrt halves the bit-length on each step, so the heap stabilizes quickly even for 10^9 inputs.

Complexity

Time
O(n + k log n)
Space
O(n)

Related patterns

  • heap
  • simulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Take Gifts From the Richest Pile and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →