Skip to content

Instantly share code, notes, and snippets.

@Mocuto
Last active October 24, 2016 16:56
Show Gist options
  • Save Mocuto/f58a4ca2f68448c145ab2374c341cb79 to your computer and use it in GitHub Desktop.
Save Mocuto/f58a4ca2f68448c145ab2374c341cb79 to your computer and use it in GitHub Desktop.
Mocuto's Awesome Solution to Sunie's Homework, in O(2^d - 1)) complexity
object Sunie {
def countFrom0to(num : Int, target : Int = 7) : Int = {
if(num < 10) {
if (num >= target) 1 else 0
}
else {
val place = logb10(num)
val count = countFrom0to(num - (num / math.pow(10, logb10(num))).toInt * math.pow(10, logb10(num)).toInt, target)
val leadDig = num / math.pow(10, place).toInt
val targetFollowedByZeros = target * math.pow(10, place)
val multipleTargetPerNum = if (num >= targetFollowedByZeros) math.min(math.pow(10, place), num - targetFollowedByZeros + 1).toInt else 0
count + (leadDig * countFrom0to(math.pow(10, place).toInt - 1, target)).toInt + multipleTargetPerNum
}
}
def countTargetInRange(a : Int, b : Int, target : Int = 7) : Int = { // Where b > a
val aCount = countFrom0to(a, target)
val bCount = countFrom0to(b, target)
bCount - aCount
}
def logb10(x : Int) : Int = (math.log(x) / math.log(10)).toInt
def lazyVersion(a : Int, b : Int, target : Int = 7) : Int = { //where b > a
(0 to b).map(_.toString).mkString.filter(_ == (target.toString())(0)).length - (0 to a).map(_.toString).mkString.filter(_ == (target.toString())(0)).length
}
def main(args : Array[String]): Unit = {
assert(lazyVersion(0, 999) == countTargetInRange(0, 999))
assert(lazyVersion(100, 150) == countTargetInRange(100, 150))
assert(lazyVersion(10, 777) == countTargetInRange(10, 777))
}
}
@rahatarmanahmed
Copy link

rahatarmanahmed commented Oct 24, 2016

Iunno scala but why (0 to b)... - (0 to a)...? can't you go (a to b)...? on line 25
EDIT: oh you do that for the good version too. maybe i don't get the problem

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment