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 <= 10001 <= gifts[i] <= 10000001 <= k <= 1000
Hints for Take Gifts From the Richest Pile
Hint 1
Simulate: each second you only need the current maximum.
Hint 2
At these sizes a linear scan for the maximum each second is fast enough; a max-heap is the scalable version.
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
- Copy the array so the input is not mutated.
- Repeat
ktimes: scan for the index of the maximum, and replace it withisqrtof its value. - 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.sqrton 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^9at 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