How to find the minimum cost to remove all elements from the array using python

Question

Given an integer array A of size N. In one operation, you can remove any element from the array, and the cost of this operation is the sum of all elements in the array present before this operation.

Find the minimum cost to remove all elements from the array.

A = [2, 1]

Given array A = [2, 1]
Remove 2 from the array => [1]. Cost of this operation is (2 + 1) = 3.
Remove 1 from the array => []. Cost of this operation is (1) = 1. So, total cost is = 3 + 1 = 4.

A = [5]

There is only one element in the array. So, cost of removing is 5.

Code is below

def solve(self, A):
        A.sort()
        if len(A) is 1:
            return A[0]
        sm = sum(A)
        for each in A:
            A.pop()
            sm += sum(A)
        return sm

I am not getting proper out. For small arrays [8,0,10 ] i got 26 which is correct output, but sometimes it fails where duplicate numbers

A = [ 579, 407, 436, 847, 929, 430, 40, 730, 608, 710, 796, 722, 48, 514, 582, 858, 634, 303, 292, 323, 869, 442, 754, 247, 10, 551, 383, 523, 878, 931, 970 ]

Here my output is 180350 The expected returned value : 204428

It would be helpful to give a concrete example of where it fails. But right away it doesn't look like `return 1` is correct if `len(A) == 1` (don't us `is` for this). The second example shows a list of length 1 and a correct answer of 5. — Mark, Sep 05 '21 at 17:49
You iterate `A` forwards **BUT** `pop()` from the other end. The result is you only process about 1/2 the items. — JonSG, Sep 05 '21 at 18:10
Another approach to the problem is, find a rule that tells you how many times each element in the sorted list will be used in a sum, and account for all of those times for an element when you reach it. Incidentally, we don't call these "arrays" in Python. — Karl Knechtel, Sep 05 '21 at 18:16

Mark · Accepted Answer · 2021-09-05T18:19:16.247

3

The main issues is that this doesn't do what you think:

for each in A:
    A.pop()
    sm += sum(A)

because you are modifying the list as you iterate it, you don't make the through all the entries. You can see this if you print A as you iterate.

A different approach is to loop while A which will stop once A is empty. This also simplifies the code:

def solve(A):
    A = sorted(A)
    sm = 0
    while A:
        sm += sum(A)
        A.pop()
    return sm

solve(l)
# 204428

You can make a nice optimization if you realized that each item gets counted as many times as its index (starting at one) -- the first element is counted once, the second twice, etc... This avoids all the inner sums:

def solution(l):
    l = sorted(l, reverse=True)
    return sum(i * n for i, n in enumerate(l,1))

solution(l)
# 204428

This should be quite a bit faster on large lists since you don't need to keep taking sums or the sub-lists

edited Sep 05 '21 at 18:19

answered Sep 05 '21 at 18:11

Mark

90,562
7
108
148

1

I'm not sure what happened, but I was running your code not mine. My code was copying the input array not modifying it, so I really am confused as to why I was getting different results. – ddejohn Sep 05 '21 at 18:15
1

Nice use of `generator expression`. – Daniel Hao Sep 05 '21 at 18:17
for i, n in enumerate(l,1), what is it mean? – Maws Sep 06 '21 at 02:26
1

@Maws `enumerate(l)` will make pairs of indexes like `(0, 579)` and `(1, 407)` where the first is the index and the second is the value in `l`. It's sometimes convenient to start at a number other than `0`, so you can pass the starting number. `enumerate(l,1)` is the same thing but starts at `1` instead of `0`. In the loop you can take each part of the pair in separate variables so `for i, n in enumerate(l,1)` mean `i` gets the index and `n` the value in each iteration. – Mark Sep 06 '21 at 02:39

How to find the minimum cost to remove all elements from the array using python

1 Answers1