DEV Community

Scala Daily Coding Problem #002

Andrew (he/him) on March 08, 2020

Daily Coding Problem is a website which will send you a programming challenge to your inbox every day. I want to show beginners how to solve some o...
Read full post
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) •

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
Collapse
 
detunized profile image
Dmitry Yakimenko • • Edited

What you're missing in your solution is the O(n) analysis. All of your solutions except the one with the division are O(n2). The shorter solution with Scala also puts a lot of pressure on the garbage collector, as it would create a lot of temporaries. That would be another type of analysis you could make on the solution. Shorter code doesn't always mean better. In this case it probably gets an order of magnitude slower because of the temporary arrays. It's not possible to observe this with such a small test example, but if you'd make the input, let's say, 10000 elements (ignoring the fact, that the multiplication would overflow), the O(n2) would take potentially hours to finish.

I see someone already suggested a O(n) (linear) solution to this problem. If you did this analysis as a part of the exercise, maybe you'd start thinking of a faster solution yourself. In reality O(n2) is too slow for any reasonable n. In many cases O(n2) is not considered practical.

I suggest that with your next exercise to reason about the time and memory complexity as well, not just the code for the algorithm.