# Smallest possible sum in Kotlin

## 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:

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([6, 9, 21]) #-> 9

### Solution steps

[6, 9, 12] #-> X[2] = 21 - 9
[6, 9, 6] #-> X[2] = 12 - 6
[6, 3, 6] #-> X[1] = 9 - 6
[6, 3, 3] #-> X[2] = 6 - 3
[3, 3, 3] #-> X[1] = 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:

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:

fun solution(numbers: LongArray): Long {
var gcdVal : Long = numbers[0]
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:

fun solution(numbers: LongArray): Long {
var array = numbers.toTypedArray()
while (!array.all { i -> i == array[0] } ) {
val min = array.min()!!
array = array.map { i ->
val mod = i % min
[email protected] if (mod != 0L) mod else min
}.toTypedArray()
}
return array.sum()
}

## Test cases to validate our solution

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)))
}
}
Tags:
Subscribe
Notify of