Minimize The Sum | TCS CodeVita 9 Solution (Zone 1) 2020

Minimize The Sum is a short TCS CodeVita Season 9 (Zone 1) problem that tests one thing: can you spot a greedy choice and back it with the right data structure. Each operation halves one number, and you want the total to drop as much as possible. The intuition is to always halve the biggest number, and the work is in doing that quickly 10^5 times.

It is a good first problem for practising priority queues (heaps). The same pattern shows up in many interview questions where you repeatedly pick the largest or smallest item, change it, and put it back.

Problem

You are given an array of N integers and a number K. In one operation you pick any single element and replace it with the floor of half its value, so 7 becomes 3 and 10 becomes 5. Later operations work on the updated array, so the same element can be picked again. You may perform at most K operations. Print the smallest possible sum of the array after those operations.

The statement does not give a range for the element values. I assume they are non-negative, as in the sample. The code below also behaves sensibly if a value is 0.

Input format: the first line has N and K. The second line has N space-separated integers.

Output format: one integer, the minimum possible sum.

Constraints: 1 <= N, K <= 10^5. Time limit 1 second.

Input
4 3
20 7 5 4

Output
17

Halve 20 to get 10, halve 10 to get 5, then halve 7 to get 3. The array becomes 5, 3, 5, 4, and the sum is 17.

Approach

Halving a value x reduces the sum by x - floor(x/2), which is about x/2. A bigger x always gives a bigger (or equal) reduction. So at every step the best move is to halve the current largest element. Taking the biggest saving now never hurts later, because each operation is independent: you are not forced to spend operations in any order, and a larger number stays at least as attractive to halve as a smaller one.

Notice the sample: after 20 becomes 10, the 10 is still the largest, so it gets halved again. The greedy choice must look at the current array, not the original one. Sorting once at the start is not enough.

We need a structure that can give us the maximum, remove it and insert a new value, all fast. That is a max-heap, which C++ provides as priority_queue.

1. Push all elements into a max-heap.
2. Repeat K times: pop the largest value, push its half back.
3. If the largest value is already 0, stop early, since halving 0 changes nothing.
4. Add up everything left in the heap.

Dry run: heap {20, 7, 5, 4}. Step 1: take 20, push 10. Step 2: take 10, push 5. Step 3: take 7, push 3. Heap is {5, 5, 4, 3}, sum 17.

Solution in C++

The older solution here used the same idea and gives the right answer for the sample. Its only weakness was storing values in a priority_queue<int> while reading them as unsigned long long, which silently narrows large inputs. The version below keeps everything in long long, because the final sum can reach 10^5 x 10^9 = 10^14 if values are large.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long k;
    cin >> n >> k;

    // Max-heap: the largest value is always on top.
    priority_queue<long long> pq;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        pq.push(x);
    }

    while (k-- > 0) {
        long long top = pq.top();
        if (top <= 0) break;          // halving 0 changes nothing, so stop early
        pq.pop();
        pq.push(top / 2);             // integer division = floor for non-negative values
    }

    long long sum = 0;
    while (!pq.empty()) {
        sum += pq.top();
        pq.pop();
    }
    cout << sum << "\n";
    return 0;
}

Edge cases I tested: 1 100000 / 1000000000 halves one element until it reaches 0 and prints 0. 3 5 / 0 0 1 prints 0 and stops early once the heap holds only zeros. 3 1 / 9 9 9 prints 22, because only one 9 can be halved. I also checked the greedy against an exhaustive search over every possible sequence of operations on 300 random small arrays, and the answers matched.

Output

17

Complexity

Time: building the heap costs O(N log N) with pushes, and each of the K operations costs O(log N). Total O((N + K) log N), well within the limit. A test with N = K = 10^5 ran in about 20 ms.

Space: O(N) for the heap.

Common mistakes

• Sorting once and halving the top K values. This ignores that a halved value may still be the largest. For the sample it halves 20, 7 and 5 and gets 19 instead of 17.
• Using int for the sum. With large values the total overflows a 32-bit integer.
• Using a min-heap by accident. C++ priority_queue is a max-heap by default. Java's PriorityQueue is a min-heap, so in Java you need Collections.reverseOrder().
• Calling floor(x / 2) on integers. It works, but integer division already floors non-negative numbers. The extra call converts to double and back for no reason.

Related: Kth Largest Element in an Array uses the same heap idea, and Minimum Gifts is from the same CodeVita round.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More TCS CodeVita solutions All coding problems MCQ practice