Take Gifts From the Richest Pile

Easy
839.

Take Gifts From the Richest Pile

Take Gifts From the Richest Pile is an easy coding problem on arrays, greedy and simulation, asked in Amazon, Microsoft and TCS interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} gifts
 * @param {number} k
 * @return {number}
 */
var pickGifts = function(gifts, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Take Gifts From the Richest Pile — Problem & Solution

Take Gifts From the Richest Pile solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Take Gifts From the Richest Pile is an easy coding problem on arrays, greedy and simulation, asked in Amazon, Microsoft and TCS interviews.

  • Difficulty: Easy
  • Topics: Arrays, Greedy, Simulation, Heap
  • Asked at: Amazon, Microsoft, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Take Gifts From the Richest Pile

  1. Hint 1

    Simulate: each second you only need the current maximum.

  2. Hint 2

    At these sizes a linear scan for the maximum each second is fast enough; a max-heap is the scalable version.

  3. Hint 3

    Compute the integer square root without floating point — binary search or a walk.

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)

Java

private static int isqrtGift(int v) {
    int lo = 0, hi = 46341;
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if ((long) mid * mid <= v) lo = mid; else hi = mid - 1;
    }
    return lo;
}

public static int pickGifts(int[] gifts, int k) {
    int[] a = gifts.clone();
    for (int t = 0; t < k; t++) {
        int mi = 0;
        for (int i = 1; i < a.length; i++) if (a[i] > a[mi]) mi = i;
        a[mi] = isqrtGift(a[mi]);
    }
    int sum = 0;
    for (int x : a) sum += x;
    return sum;
}

C++

static int isqrtGift(int v) {
    int lo = 0, hi = 46341;
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if ((long long) mid * mid <= v) lo = mid; else hi = mid - 1;
    }
    return lo;
}

int pickGifts(vector<int>& gifts, int k) {
    vector<int> a = gifts;
    for (int t = 0; t < k; t++) {
        int mi = 0;
        for (int i = 1; i < (int) a.size(); i++) if (a[i] > a[mi]) mi = i;
        a[mi] = isqrtGift(a[mi]);
    }
    int sum = 0;
    for (int x : a) sum += x;
    return sum;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms