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:
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:
Ideally the
.init
and.tail
wouldn't be necessary, but it seems likescanLeft
andscanRight
add the "initial" value (1)Smart! You can avoid calculating and then removing that extra element by calling
init
andtail
before youscan
: