Discussion on: Scala Daily Coding Problem #002

View post

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 }
    }

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

Andrew (he/him) • Mar 8 '20

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)