Minimum Operations to Halve Array Sum - Practice Coding Problems

Minimum Operations to Halve Array Sum - Problem

You are given an array nums of positive integers. In one operation, you can choose any number from nums and reduce it to exactly half the number. (Note that you may choose this reduced number in future operations.)

Return the minimum number of operations to reduce the sum of nums by at least half.

Input & Output

Example 1 — Basic Case

$ Input: nums = [5,19,8,1]

› Output: 3

💡 Note: Original sum = 33, target reduction ≥ 16.5. Operations: halve 19→9.5 (reduction=9.5), halve 9.5→4.75 (total=14.25), halve 8→4 (total=18.25≥16.5). Answer: 3 operations.

Example 2 — Small Array

$ Input: nums = [3,8,20]

› Output: 3

💡 Note: Original sum = 31, target reduction ≥ 15.5. Operations: halve 20→10 (reduction=10), halve 10→5 (total=15), halve 8→4 (total=19≥15.5). Answer: 3 operations.

Example 3 — Edge Case

$ Input: nums = [1,1]

› Output: 2

💡 Note: Original sum = 2, target reduction ≥ 1. Operations: halve 1→0.5 (reduction=0.5), halve 1→0.5 (total=1≥1). Answer: 2 operations.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Array [5,19,8,1] with sum=33, need reduction≥16.5

Process

Greedily halve largest elements: 19→9.5→4.75, then 8→4

Output

3 operations needed to achieve target reduction

Key Takeaway

🎯 Key Insight: Always halve the largest element for maximum reduction impact per operation

Asked in

a Amazon 35 G Google 28 M Microsoft 22 f Meta 15

The key insight is that to minimize operations, we should always halve the largest element for maximum sum reduction. The optimal approach uses a max heap to efficiently track the largest element. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Max Heap (Optimal)	O(n log n)	O(n)	Use max heap to efficiently track and extract the largest element for halving
Brute Force - Try All Combinations	O(2^n)	O(n)	Try all possible sequences of operations until sum is halved
Greedy with Sorting	O(n² log n)	O(1)	Sort array, repeatedly halve the largest element until sum is reduced by half

Max Heap (Optimal) — Algorithm Steps

Create max heap from all elements
Calculate target reduction
While reduction < target:
Extract max from heap
Halve it, add reduction, push back to heap
Return operations count

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Max Heap

Create heap with [19,8,5,1] at root

Extract & Halve

Pop max, halve it, push back

Repeat

Heap maintains largest element at top

Code -

solution.c — C

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

// Simple max heap implementation
typedef struct {
    double* data;
    int size;
    int capacity;
} MaxHeap;

MaxHeap* createHeap(int capacity) {
    MaxHeap* heap = (MaxHeap*)malloc(sizeof(MaxHeap));
    heap->data = (double*)malloc(capacity * sizeof(double));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void heapifyUp(MaxHeap* heap, int idx) {
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (heap->data[parent] >= heap->data[idx]) break;
        double temp = heap->data[parent];
        heap->data[parent] = heap->data[idx];
        heap->data[idx] = temp;
        idx = parent;
    }
}

void heapifyDown(MaxHeap* heap, int idx) {
    while (1) {
        int largest = idx;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        
        if (left < heap->size && heap->data[left] > heap->data[largest])
            largest = left;
        if (right < heap->size && heap->data[right] > heap->data[largest])
            largest = right;
        
        if (largest == idx) break;
        double temp = heap->data[idx];
        heap->data[idx] = heap->data[largest];
        heap->data[largest] = temp;
        idx = largest;
    }
}

void push(MaxHeap* heap, double val) {
    heap->data[heap->size] = val;
    heapifyUp(heap, heap->size);
    heap->size++;
}

double pop(MaxHeap* heap) {
    double max = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0);
    return max;
}

int solution(int* nums, int numsSize) {
    double originalSum = 0;
    for (int i = 0; i < numsSize; i++) {
        originalSum += nums[i];
    }
    double target = originalSum / 2;
    
    MaxHeap* maxHeap = createHeap(numsSize * 2);
    for (int i = 0; i < numsSize; i++) {
        push(maxHeap, nums[i]);
    }
    
    int operations = 0;
    double currentReduction = 0;
    
    while (currentReduction < target) {
        double maxVal = pop(maxHeap);
        double newVal = maxVal / 2;
        currentReduction += maxVal - newVal;
        push(maxHeap, newVal);
        operations++;
    }
    
    free(maxHeap->data);
    free(maxHeap);
    return operations;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,2,3] format
    int nums[1000];
    int count = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, count));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Building heap takes O(n), each of O(n) operations takes O(log n) for heap operations

⚡ Linearithmic

Space Complexity

O(n)

Max heap stores all n elements

⚡ Linearithmic Space

32.1K Views

Medium Frequency

~25 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

Max Heap (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler