Question

DE Shaw Coding Round Question : (On campus) | Set - 23 | 2022

Answer 1

max heap
Time: O(nlogn) + O(klogn)
Space: O(n)

public class Solution {
    public static int chocolatesRemained(int[] chocolates,int iterations){
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->(b-a));
        for(int i=0;i<chocolates.length;i++){
            q.offer(chocolates[i]);
        }
        while(iterations > 0){
            int curr = q.poll();
            curr = (int) Math.sqrt(curr);
             q.offer(curr);
            iterations--;
        }
        int remainedChocolates = 0;
        while(!q.isEmpty()){
            remainedChocolates+=q.poll();
        }
        return remainedChocolates;
    }
    public static void main(String[] args) {
        int[] chocolates = {25, 64, 9, 4, 100};
        int iterations = 4;
        System.out.println(chocolatesRemained(chocolates,iterations));//29
    }
}

Answer 2

DE Shaw Coding Round Question : (On campus)
There is an array of pile of chocolates, in every iteration Ayushi chose pile with maximum number of chocolates, after that square root of chocolate remains and rest is eaten by Ayushi. After k iterations find number of chocolates remaining.

Input Format
It consist of 3 lines.
First line contain n (size of pile)
Second line contains n space separated integers
Third line contains k (no. of iteration)

Output Format:
print one integer the total sum of chocolates remaining.

Sample Input:
5
25 64 9 4 100
4

Sample Output:
29