initial
We want to choose the 2 smallest values and pop them and append them back with the added sum (small1+small2) twice. I immediately thought of using heap instead of sorting the list each time of m but I thought something goes weird with heaps and duplicates. (tbc)
Anyway I used list.sort(reverse=True) which obviously is more time inefficient (X4 more inefficient) but I used list.pop() instead of list.pop(0) because pop() pops the last element of list and is o(1). o(1) because we dont have to shift the entire list to the left like pop(0) which pops the element at the beginnig
revisited
yes immediately thought of heap and apparently heaps allow duplicates. I cant rmb that question where it was weird that it didnt allow duplicates
solution
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n,m= map(int,input().split())
lst = list(map(int,input().split()))
for _ in range(m):
lst.sort(reverse=True)
val = lst.pop()+lst.pop()
lst.append(val)
lst.append(val)
print(sum(lst))using heap(x4 more eff.)
import heapq
n,m=map(int,input().split())
st=list(map(int,input().split()))
def solution(m,st):
heapq.heapify(st)
for _ in range(m):
x_y=heapq.heappop(st)+heapq.heappop(st)
heapq.heappush(st,x_y)
heapq.heappush(st,x_y)
return sum(st)
print(solution(m,st))complexity
n time and space? wrong! sorting is n log (n) and since we are doing this sort m times, it is mn log(n) time.
The given code processes the list lst in a loop where, at each iteration, it sorts the list in reverse order, takes the two largest elements, sums them, and then appends the sum twice back to the list. This process continues for m iterations.
The time complexity of the code depends on the sorting operation inside the loop, which is the most time-consuming part. The sorting operation is performed on a list of length n, and it has a time complexity of O(n log(n)). Since the sorting is done within a loop that runs m times, the overall time complexity is O(m n * log(n)).
The space complexity of the code is O(n) since it creates and maintains a list of length n.
So, the time complexity is O(m n log(n)), and the space complexity is O(n).
