Smallest possible sum in Kotlin

2 min read 412 words

Table of Contents

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

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()
}

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
            return@map 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:
Andrew
Andrew

Andrew is a visionary software engineer and DevOps expert with a proven track record of delivering cutting-edge solutions that drive innovation at Ataiva.com. As a leader on numerous high-profile projects, Andrew brings his exceptional technical expertise and collaborative leadership skills to the table, fostering a culture of agility and excellence within the team. With a passion for architecting scalable systems, automating workflows, and empowering teams, Andrew is a sought-after authority in the field of software development and DevOps.

Tags

Recent Posts