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
Code language: PHP (php)

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

Example

solution([6, 9, 21]) #-> 9
Code language: CSS (css)

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
Code language: PHP (php)

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.

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() }
Code language: Kotlin (kotlin)

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) }
Code language: Kotlin (kotlin)

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 return@map if (mod != 0L) mod else min }.toTypedArray() } return array.sum() }
Code language: Kotlin (kotlin)

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))) } }
Code language: Kotlin (kotlin)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments