Day 24 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/minimum-steps-to-halve-sum/1

Minimum Steps to Halve Sum

Difficulty: Medium Accuracy: 62.81%

Given an array arr[], find the minimum number of operations required to make the sum of its elements less than or equal to half of the original sum. In one operation, you may replace any element with half of its value (with floating-point precision).

Examples:
Input: arr[] = [8, 6, 2]
Output: 3
Explanation: Initial sum = (8 + 6 + 2) = 16, half = 8
Halve 8 → arr[] = [4, 6, 2], sum = 12 (still 12 > 8)
Halve 6 → arr[] = [4, 3, 2], sum = 9 (still 9 > 8)
Halve 2 → arr[] = [4, 3, 1], sum = 8.
Input: arr[] = [9, 1, 2]
Output: 2
Explanation: Initial sum = 12, half = 6
Halve 9 → arr[] = [4.5, 1, 2], sum = 7.5 (still > 6)
Halve 4.5 → arr[] = [2.25, 1, 2], sum = 5.25 ≤ 6
Constraints:
1 ≤ arr.size() ≤ 105
0 ≤ arr[i] ≤ 104

Solution:
import heapq

class Solution:
def minOperations(self, arr):
total = sum(arr)
target = total / 2
heap = [-x for x in arr]
heapq.heapify(heap)
ops, reduced = 0, 0

    while total - reduced > target:
        val = -heapq.heappop(heap)
        half = val / 2
        reduced += half
        heapq.heappush(heap, -half)
        ops += 1

    return ops