Moduli number system in Kotlin

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")
        
    }
}
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments