Take Gifts From the Richest Pile - Practice Coding Problems

Take Gifts From the Richest Pile - 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.
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.

Input & Output

Example 1 — Basic Operation

$ Input: gifts = [25,64,9,4,100], k = 4

› Output: 29

💡 Note: Second 1: Take 100 → √100 = 10, array becomes [25,64,9,4,10]. Second 2: Take 64 → √64 = 8, array becomes [25,8,9,4,10]. Second 3: Take 25 → √25 = 5, array becomes [5,8,9,4,10]. Second 4: Take 10 → √10 = 3, array becomes [5,8,9,4,3]. Sum = 5+8+9+4+3 = 29

Example 2 — Single Pile

$ Input: gifts = [1], k = 4

› Output: 1

💡 Note: Only one pile with 1 gift. After any number of operations: √1 = 1, so it remains [1]. Sum = 1

Example 3 — Small Values

$ Input: gifts = [4,4,4], k = 2

› Output: 8

💡 Note: Second 1: Take any 4 → √4 = 2, array becomes [4,4,2]. Second 2: Take any 4 → √4 = 2, array becomes [2,2,2]. Sum = 2+2+2 = 6. Wait, let me recalculate: [4,4,4] → [2,4,4] → [2,2,4]. Sum = 2+2+4 = 8

Constraints

1 ≤ gifts.length ≤ 10³
1 ≤ gifts[i] ≤ 10⁹
1 ≤ k ≤ 10³

Visualization

Tap to expand

Understanding the Visualization

Input

Array of gift piles and number of seconds k

Process

Each second: find max pile, replace with floor(√max)

Output

Sum of all remaining gifts after k seconds

Key Takeaway

🎯 Key Insight: Use a max heap to efficiently find the largest pile in O(log n) time instead of scanning the entire array

Asked in

A Amazon 15 M Microsoft 10 G Google 8

The key insight is to efficiently find the maximum pile each second. The max heap approach is optimal, providing O(k log n) time complexity by maintaining the largest element at the heap root. This eliminates the need for linear scans. Time: O(k log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Linear Search	O(n×k)	O(1)	Find maximum pile by scanning entire array each time
Max Heap - Priority Queue	O(n + k log n)	O(n)	Use max heap to efficiently find and update the largest pile

Brute Force - Linear Search — Algorithm Steps

For each second from 1 to k:
Scan array to find maximum value and its index
Replace maximum with floor(sqrt(maximum))
Continue until k seconds complete

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Maximum

Scan array linearly to find largest pile

Apply Square Root

Replace maximum with floor(sqrt(max))

Repeat

Continue for k seconds

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

long long solution(int* gifts, int giftsSize, int k) {
    for (int second = 0; second < k; second++) {
        int maxIdx = 0;
        for (int i = 1; i < giftsSize; i++) {
            if (gifts[i] > gifts[maxIdx]) {
                maxIdx = i;
            }
        }
        gifts[maxIdx] = (int) sqrt(gifts[maxIdx]);
    }
    long long sum = 0;
    for (int i = 0; i < giftsSize; i++) {
        sum += gifts[i];
    }
    return sum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int gifts[1000];
    int giftsSize = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        gifts[giftsSize++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    int k;
    scanf("%d", &k);
    printf("%lld\n", solution(gifts, giftsSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×k)

For each of k seconds, we scan n piles to find maximum

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler