## Description

Given an array X of positive integers, its elements are to be transformed by running the following operation on them as many times as required:

```if X[i] > X[j] then X[i] = X[i] - X[j]```

When no more transformations are possible, return its sum ("smallest possible sum").

For instance, the successive transformation of the elements of input X = [6, 9, 21] is detailed below:
```
X_1 = [6, 9, 12] # -> X_1[2] = X[2] - X[1] = 21 - 9
X_2 = [6, 9, 6]  # -> X_2[2] = X_1[2] - X_1[0] = 12 - 6
X_3 = [6, 3, 6]  # -> X_3[1] = X_2[1] - X_2[0] = 9 - 6
X_4 = [6, 3, 3]  # -> X_4[2] = X_3[2] - X_3[1] = 6 - 3
X_5 = [3, 3, 3]  # -> X_5[1] = X_4[0] - X_4[1] = 6 - 3
```
The returning output is the sum of the final transformation (here 9).

## Example

## Solution steps:

## Additional notes:

There are performance tests consisted of very big numbers and arrays of size at least 30000. Please write an efficient algorithm to prevent timeout.

Difficulty: interview

Starter code:

def solution(a):
	

Solutions:
from fractions import gcd
from functools import reduce

def solution(a):
    return reduce(gcd, a) * len(a)

def solution(a):
    a_len = len(a)
    a = set(a)
    while len(a) != 1:
        b = max(a)
        a.remove(b)
        a.add(b-max(a))
    return(max(a) * a_len)

from fractions import gcd
from functools import reduce

def solution(a):
    return len(a) * reduce(gcd, a)

import sys
if sys.version_info.major >= 3:
    from functools import reduce
if sys.version_info < (3,5):
    from fractions import gcd
elif sys.version_info >= (3,5):
    from math import gcd

def solution(a):
    return reduce(gcd, a) * len(a)

from functools import reduce

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

def solution(a):
    return len(a) * reduce(gcd, a)

from math import gcd
from functools import reduce
solution=lambda a:reduce(gcd,a)*len(a)

def solution(a):
    elem = min(a)
    m = elem
    for i in range(len(a)):
        if (a[i] % elem != 0):
            elem = a[i] % elem
            if (m % elem != 0):
                elem = m % elem
    return abs(elem*len(a))


def solution(a):
    len_a = len(a)
    a = set(a)
    while len(a) > 1:
        max_a = max(a)
        a.remove(max_a)
        a.add(max_a - max(a))
    return a.pop() * len_a


def gcd(x, y):
    if x < y:
        x, y = y, x
    while y:
        x, y = y, x % y
    return x

def solution(arr):
    uniques = list(set(arr))
    N = len(arr)
    if N < 2 or len(uniques) == 1:
        return arr[0] * N
        
    min_gcd = gcd(uniques[0], uniques[1])
    for i in range(2, len(uniques)):
        if min_gcd == 1:
            return N
        cur = gcd(min_gcd, uniques[i])
        min_gcd = min(cur, min_gcd)
            
    return min_gcd * N

from fractions import gcd
from functools import reduce
solution = lambda a: reduce(gcd, a)*len(a)