DEV Community

loading...

Discussion on: Scala Daily Coding Problem #002

Collapse
curtisfenner profile image
Curtis Fenner • Edited

There's a straightforward linear-time algorithm that solves this without division -- compute the cumulative products from the left, and from the right, then multiply pairwise. I think this algorithm can be expressed very nicely in Scala.

I'm not super familiar with Scala, but here's my best attempt:

    def productExcept(arr: Array[Int]): Array[Int] = {
        val fromLeft = arr.scanLeft(1)(_ * _).init
        val fromRight = arr.scanRight(1)(_ * _).tail
        fromLeft.zip(fromRight).map { case (a, b) => a * b }
    }
Enter fullscreen mode Exit fullscreen mode

Ideally the .init and .tail wouldn't be necessary, but it seems like scanLeft and scanRight add the "initial" value (1)

Collapse
awwsmm profile image
Andrew (he/him) Author

Smart! You can avoid calculating and then removing that extra element by calling init and tail before you scan:

scala> arr.scanLeft(1)(_ * _).init
res30: Array[Int] = Array(1, 1, 2, 6, 24)

scala> arr.scanRight(1)(_ * _).tail
res31: Array[Int] = Array(120, 60, 20, 5, 1)

scala> arr.init.scanLeft(1)(_ * _)
res32: Array[Int] = Array(1, 1, 2, 6, 24)

scala> arr.tail.scanRight(1)(_ * _)
res33: Array[Int] = Array(120, 60, 20, 5, 1)
Enter fullscreen mode Exit fullscreen mode