Problem statement

https://binarysearch.com/problems/One-Integer/

Solution

Equal to Leetcode 1167 Minimum Cost to Connect Sticks.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        heapify(nums)
        ans = 0
        for _ in range(len(nums) - 1):
            a, b = heappop(nums), heappop(nums)
            ans += (a + b)
            heappush(nums, a + b)

        return ans