The challenge
A number system with moduli is defined by a vector of k moduli, [m1,m2, ···,mk].
The moduli must be pairwise co-prime, which means that, for any pair of moduli, the only common factor is 1.
In such a system each number n is represented by a string "-x1--x2-- ... --xk-" of its residues, one for each modulus. The product m1 * ... * mk must be greater than the given number n which is to be converted in the moduli number system.
For example, if we use the system [2, 3, 5] the number n = 11 is represented by "-1--2--1-",
the number n = 23 by "-1--2--3-".
If we use the system [8, 7, 5, 3] the number n = 187 becomes "-3--5--2--1-".
You will be given a number n (n >= 0) and a system S = [m1,m2, ···,mk] and you will return a string "-x1--x2-- ...--xk-" representing the number n in the system S.
If the moduli are not pairwise co-prime or if the product m1 * ... * mk is not greater than n, return "Not applicable".
Examples:
(you can add them in the “Sample tests”)
fromNb2Str(11, [2,3,5]) -> "-1--2--1-"
fromNb2Str(6, [2, 3, 4]) -> "Not applicable", since 2 and 4 are not coprime
fromNb2Str(7, [2, 3]) -> "Not applicable" since 2 * 3 < 7
The solution in Kotlin
Option 1:
package solution
import java.math.BigInteger
object ModSystem {
fun fromNb2Str(n: Int, sys: IntArray): String {
if (sys.reduce { acc, i -> acc * i } <= n) return "Not applicable"
sys.forEachIndexed { index, a -> sys.drop(index + 1).forEach { b ->
if (a.toBigInteger().gcd(b.toBigInteger()) > BigInteger.ONE) return "Not applicable"
} }
return sys.joinToString("") { "-${n % it}-" }
}
}
Option 2:
package solution
object ModSystem {
fun fromNb2Str(n: Int, sys: IntArray): String {
return when {
sys.reduce {acc, i -> acc * i} <= n -> "Not applicable"
sys.count { it % 2 == 0} > 1 -> "Not applicable"
else -> sys.map { n % it}.joinToString(
prefix = "-",
postfix = "-",
separator = "--"
)
}
}
}
Option 3:
package solution
import kotlin.collections.*
object ModSystem {
fun product(sys: IntArray) = sys.fold(1) { acc, e -> acc * e }
tailrec fun gcd(a: Int, b: Int): Int = if(a == 0) b else gcd(b%a, a)
fun pairWiseCoprime(sys: IntArray): Boolean{
val arr = sys.toCollection(ArrayList())
do{
val head = arr.removeAt(0)
for(el in arr) if(gcd(el, head) != 1) return false
} while ( arr.isNotEmpty() )
return true
}
fun fromNb2Str(n: Int, sys: IntArray): String {
if(!pairWiseCoprime(sys) || product(sys) <= n) return "Not applicable"
return sys.map { n % it }.joinToString(separator = "--", prefix = "-", postfix = "-")
}
}
Test cases to validate our solution
package solution
import org.junit.Test
import kotlin.test.assertEquals
class ModSystemTest {
private fun testing(n: Int, bases: IntArray, expect: String) {
val actual: String = ModSystem.fromNb2Str(n, bases)
assertEquals(expect, actual)
}
@Test
fun basicTests() {
testing(779, intArrayOf(8,7,5,3), "-3--2--4--2-")
testing(187, intArrayOf(8,7,5,3), "-3--5--2--1-")
testing(259, intArrayOf(8,7,5,3), "-3--0--4--1-")
testing(15, intArrayOf(8,6,5,3), "Not applicable")
testing(15, intArrayOf(3, 2), "Not applicable")
}
}