Take Gifts From the Richest Pile — Easy Problem & Solution

Problem statement

Each second for k seconds you pick the pile with the most gifts (any one of them if tied), leave behind the number of gifts equal to the floor of its square root, and take the rest away.

Return the total number of gifts left after k seconds.

Example 1

Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation: The richest pile is reduced each second: 100 → 10, then 64 → 8, then 25 → 5, then 10 → 3, leaving 5 + 8 + 9 + 4 + 3.

Example 2

Input: gifts = [1,1,1,1], k = 4
Output: 4
Explanation: The square root of 1 is 1, so nothing changes.

Example 3

Input: gifts = [16,9,4], k = 1
Output: 17
Explanation: 16 becomes 4, leaving 4 + 9 + 4.

Constraints

• 1 <= gifts.length <= 1000
• 1 <= gifts[i] <= 1000000
• 1 <= k <= 1000

How to solve Take Gifts From the Richest Pile

A direct simulation. Each second, locate the largest pile and replace it with its integer square root; after k seconds sum what is left.

Approach

1. Copy the array so the input is not mutated.
2. Repeat k times: scan for the index of the maximum, and replace it with isqrt of its value.
3. Return the sum.

Why it works

The rule names exactly which pile to touch, so there is no choice to optimise — the 'greedy' is the problem statement. The only care needed is the square root: a floating-point sqrt can round x² to just below x, producing an off-by-one, so an integer method is safer.

Complexity

• Time — O(k · n) with a linear scan, O(k log n) with a heap
• Space — O(n)

Pitfalls

• Math.sqrt on a perfect square can land a hair below it in floating point; verify or use integer search.
• Piles of 1 stay at 1 forever, so the loop must not assume progress.
• The total reaches 10^9 at the stated limits.

Reference solution

Python

from typing import List

def pickGifts(gifts: List[int], k: int) -> int:
    def isqrt(v: int) -> int:
        lo, hi = 0, 46341
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if mid * mid <= v:
                lo = mid
            else:
                hi = mid - 1
        return lo

    a = list(gifts)
    for _ in range(k):
        mi = 0
        for i in range(1, len(a)):
            if a[i] > a[mi]:
                mi = i
        a[mi] = isqrt(a[mi])
    return sum(a)

JavaScript

var pickGifts = function(gifts, k) {
    var isqrt = function(v) {
        var lo = 0, hi = 46341;
        while (lo < hi) {
            var mid = Math.ceil((lo + hi) / 2);
            if (mid * mid <= v) lo = mid; else hi = mid - 1;
        }
        return lo;
    };
    var a = gifts.slice();
    for (var t = 0; t < k; t++) {
        var mi = 0;
        for (var i = 1; i < a.length; i++) if (a[i] > a[mi]) mi = i;
        a[mi] = isqrt(a[mi]);
    }
    var sum = 0;
    for (var j = 0; j < a.length; j++) sum += a[j];
    return sum;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy