Skip to content

Instantly share code, notes, and snippets.

@mayonesa
Last active February 6, 2022 22:25
Show Gist options
  • Save mayonesa/28344c30c2e394aa5eaac8774ba45b13 to your computer and use it in GitHub Desktop.
Save mayonesa/28344c30c2e394aa5eaac8774ba45b13 to your computer and use it in GitHub Desktop.
Given a string representation of a number, returns the number of variations of said input that is divisible by 3
/* Divisible by 3
--------------
Given a string representation of a number, returns the number of variations of said input that is divisible by 3. The variations consist of changing one digit for each variation.
For example, "21"'s variations are:
01
11
21
31
41
51
61
71
81
91
20
21
22
23
24
25
26
27
28
29
Of those,
21, 24, 27, 81, 51
are divisible by 3. So, the method should return its cardinality or 5.
*/
object DivBy3 {
def soln(s: String): Int = {
val n = s.length
(0 until n).foldLeft((0, Set.empty[String])) { case ((nDivs0, done0), i) =>
val prefix = s.substring(0, i)
val suffix = s.substring(i + 1, n)
(0 to 9).foldLeft((nDivs0, done0)) { case ((nDivs, done), d) =>
val int = prefix + d + suffix
if (done(int))
(nDivs, done)
else {
val nDivs1 = nDivs + (if (divisibleBy3(int)) 1 else 0)
(nDivs1, done + int)
}
}
}._1
}
private def divisibleBy3(int: String) = int.toInt % 3 == 0
}
import org.scalatest.flatspec.AnyFlatSpec
class DivBy3Spec extends AnyFlatSpec {
"0081" should "11" in {
assert(DivBy3.soln("0081") === 11)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment