Sorting list in Python (another way)

Question

So here is the problem:

Input an array of positive integers and need to return sum of all elements in new array with conditions: if Array[i] > Array[j] then Array[i] = Array[i] - Array[j]. Example:

[1,2,3] => [1,2,1] => [1,1,1] => output: 3

My code:

def solution(a):
    while max(a) != min(a):
        u = max(a)
        a[a.index(u)] = u - min(a) 
    return (a[0] * len(a))

But this code is very slow, how can I refactor it for better performance ?

Are you looking to do this manually? In other words, you don't want to use sorted? Because it is a bit funny that you are using max and min, but not sorted. — idjaw
– idjaw, Commented Jul 26, 2017 at 15:17
min, max and index are O(n), this is what makes the code slow. — ForceBru
– ForceBru, Commented Jul 26, 2017 at 15:18
this code outputs one integer value, not a list. you'll need to explain your problem more clearly. give an example of expected input/output — sam-pyt
– sam-pyt, Commented Jul 26, 2017 at 15:18
You aren't sorting anything here, you're just applying this formula, that's all. — ForceBru
– ForceBru, Commented Jul 26, 2017 at 15:21
@ForceBru. You took the words right out of my mouth. The description does not match the code very well. — Mad Physicist
– Mad Physicist, Commented Jul 26, 2017 at 15:21

Jared Goguen · Accepted Answer · 2017-07-26 15:50:34Z

2

The code you implemented roughly applies the Euclidean algorithm to a group of numbers. The following code is equivalent to yours, but more efficient:

from fractions import gcd

a = [1, 2, 3]
print reduce(gcd, a) * len(a) # 3

Whether or not your code does what you want it to do is another story. In Python 3.X, reduce will have to be imported from functools.

edited Jul 26, 2017 at 15:50

answered Jul 26, 2017 at 15:37

Jared Goguen

9,0182 gold badges22 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Денис Милованов Over a year ago

Thank you. How many tools in Python I don`t know. Your code work perfectly

Collectives™ on Stack Overflow

Sorting list in Python (another way)

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related