## The challenge

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:

 ``````1 2 3 4 5 `````` ``````X_1 = [6, 9, 12] # -> X_1 = X - X = 21 - 9 X_2 = [6, 9, 6] # -> X_2 = X_1 - X_1 = 12 - 6 X_3 = [6, 3, 6] # -> X_3 = X_2 - X_2 = 9 - 6 X_4 = [6, 3, 3] # -> X_4 = X_3 - X_3 = 6 - 3 X_5 = [3, 3, 3] # -> X_5 = X_4 - X_4 = 6 - 3 ``````

The returning output is the sum of the final transformation (here 9).

### Example

 ``````1 `````` ``````solution([6, 9, 21]) #-> 9 ``````

### Solution steps

 ``````1 2 3 4 5 `````` ``````[6, 9, 12] #-> X = 21 - 9 [6, 9, 6] #-> X = 12 - 6 [6, 3, 6] #-> X = 9 - 6 [6, 3, 3] #-> X = 6 - 3 [3, 3, 3] #-> X = 6 - 3 ``````

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

## The solution in Kotlin

Option 1:

 ``````1 2 3 4 `````` ``````fun solution(n: LongArray): Long { fun gcd(a: Long, b: Long): Long = if (b == 0L) a else gcd(b, a % b) return n.toList().reduce { acc, l -> gcd(acc, l) } * n.count() } ``````

Option 2:

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````fun solution(numbers: LongArray): Long { var gcdVal : Long = numbers for (i in numbers.indices) { gcdVal = gcd(gcdVal, numbers[i]) } return gcdVal * numbers.size } fun gcd(a: Long, b: Long): Long { return if (a == 0L) b else gcd(b % a, a) } ``````

Option 3:

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````fun solution(numbers: LongArray): Long { var array = numbers.toTypedArray() while (!array.all { i -> i == array } ) { val min = array.min()!! array = array.map { i -> val mod = i % min return@map if (mod != 0L) mod else min }.toTypedArray() } return array.sum() } ``````

## Test cases to validate our solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 `````` ``````import kotlin.test.assertEquals import org.junit.Test class TestExample { @Test fun `Basic tests`() { assertEquals(9, solution(longArrayOf(6,9,21))) assertEquals(3, solution(longArrayOf(1,21,55))) assertEquals(5, solution(longArrayOf(3,13,23,7,83))) assertEquals(923, solution(longArrayOf(71,71,71,71,71,71,71,71,71,71,71,71,71))) assertEquals(22, solution(longArrayOf(11,22))) assertEquals(2, solution(longArrayOf(5,17))) assertEquals(12, solution(longArrayOf(4,16,24))) assertEquals(9, solution(longArrayOf(9))) } } ``````