[scala] - modulo arithmetic step by step guide
Intuition\nIn order to count anagrams we should count permutations of letters for each word and multiply them. Permutations are computed with factorial. The sim
# Intuition\nIn order to count anagrams we should count permutations of letters for each word and multiply them. Permutations are computed with factorial. The simplest solution looks like this:\n\n```scala\nval m = 1000000007\n\ndef countAnagrams(s: String): Int = {\n  val wordCounts = s.split(\' \').map { word =>\n    val charCounts = word.groupBy(identity).map(pair => factorial(pair._2.length()))\n    factorial(word.length()) / charCounts.reduce(_ * _)\n  }\n  wordCounts.reduce(_ * _).mod(m).toInt\n}\n\ndef factorial(n: Int): BigInt = BigInt(2.to(n).foldLeft(1)((acc, el) => acc * el % m))\n```\nHowever, the solution fails the performance test case. To count it effectively we should switch to modulo arithmetics.\nNotice, that we require only four operations in our algebra:\n```scala\ntrait Arithmetic[T] {\n  def factorial(n: Int): T\n  def multiply(a: T, b: T): T\n  def division(a: T, b: T): T\n  def toInt(n: T): Int\n}\n```\n\nThe original solution can be rewritten in terms of this trait:\n```scala\ndef doCount[T](s: String, ar: Arithmetic[T]): Int = {\n  val wordCounts = s.split(\' \').toList.map { word =>\n    val charCounts = word.groupBy(identity).map(pair => ar.factorial(pair._2.length))\n    ar.division(ar.factorial(word.length()), charCounts.reduce(ar.multiply))\n  }\n  ar.toInt(wordCounts.reduce(ar.multiply))\n}\n```\nwith the corresponding arithemtic:\n```scala\nfinal class BigIntModuloArithmetic(m: Int) extends Arithmetic[BigInt] {\n  def factorial(n: Int): BigInt = 2.to(n).foldLeft(BigInt(1))((acc, el) => acc * el)\n  def multiply(a: BigInt, b: BigInt): BigInt = a * b\n  def division(a: BigInt, b: BigInt): BigInt = a / b\n  def toInt(n: BigInt): Int = (n % m).toInt\n}\n```\nWe can verify that this code works the same as the original solution using\n```scala\ndef countAnagrams(s: String): Int =\n  doCount(s, new BigIntModuloArithmetic(1000000007))\n```\n\nLastly, we need to implement modulo arithmetic. `factorial`, `multiply` and `toInt` are trivial, whereas `division` is not.\n```scala\nfinal class IntModuloArithmetic(mInt: Int) extends Arithmetic[Int] {\n  private val m = BigInt(mInt)\n  def factorial(n: Int): Int = 2.to(n).foldLeft(1)((acc, el) => multiply(acc, el))\n  def multiply(a: Int, b: Int): Int = (BigInt(a) * BigInt(b)).mod(m).toInt\n  def division(a: Int, b: Int): Int = (BigInt(b).modInverse(m) * a).mod(m).toInt\n  def toInt(n: Int): Int = n\n}\n```\nTo verify the implementation we need to change the implementation of `countAnagram` \n```scala\ndef countAnagrams(s: String): Int =\n  doCount(s, new IntModuloArithmetic(1000000007))\n```
['Scala']