DEV Community

loading...

Scala Daily Coding Problem #002

awwsmm profile image Andrew (he/him) Updated on ・4 min read

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 of these problems using Scala, so this will be an ongoing series of my solutions. Feel free to pick them apart in the comments!

Problem

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can't use division?

Strategy

See my discussion of this problem (and my Java implementation) here!

Code

We could solve this problem using nearly the exact same code as from my Java solution. Here is that Java code:

  public static int[] codingProblem002 (int[] given) {

    final int len = given.length;
    int[] retval = new int[len];

    // initialise all elements of `retval` to 1
    Arrays.fill(retval, 1);

    for (int i = 0; i < len; ++i) {
      for (int j = 0; j < len; ++j) {
        if (j == i) continue;
        retval[j] *= given[i];
      }
    }

    return retval;
  }
Enter fullscreen mode Exit fullscreen mode

...and here it is translated into Scala

def codingProblem002 (given: Array[Int]): Array[Int] = {
  val len: Int = given.length
  val retval: Array[Int] = new Array[Int](len)

  // initialise all elements of `retval` to 1
  java.util.Arrays.fill(retval, 1)

  for (i <- 0 until len) {
    for (j <- 0 until len) {
      if (j != i) retval(j) *= given(i)
    }
  }

  return retval
}
Enter fullscreen mode Exit fullscreen mode

It was actually a bit painful to write that using Scala. I had to fight against common Scala idioms to get this into a "Java-like", imperative style. For instance, in Scala, we can use a for comprehension, rather than a for loop. While in Java, we might write something like

    for (int i = 0; i < len; ++i) {
      for (int j = 0; j < len; ++j) {
        if (j == i) continue;
        retval[j] *= given[i];
      }
    }
Enter fullscreen mode Exit fullscreen mode

...in Scala, this might be rewritten as something like

  for {
    i <- 0 until len
    j <- 0 until len
    if (j != i)
  } retval(j) *= given(i)
Enter fullscreen mode Exit fullscreen mode

...but even this feels quite unnatural. Scala tends toward the functional programming paradigm, which emphasises immutability, and discourages objects with mutable state, like the retval array in the example above.

So how might we solve this problem without a mutable array? Let's think about what we're trying to do. What we're really doing is mapping each element of the given array to a corresponding element in a new array of the same length. We should be able to use Scala's map method on the given array, then:

given.map(each => ???)
Enter fullscreen mode Exit fullscreen mode

...and we want to map each element to a product, which is the product of all elements of the given array except the current (each) element. We remove a particular element from an array by using the dropRight and drop methods on the Array:

scala> given
res9: Array[Int] = Array(1, 2, 3, 4, 5)

scala> val i = 3
i: Int = 3

scala> given.dropRight(given.length-i) ++ given.drop(i+1)
res10: Array[Int] = Array(1, 2, 3, 5)
Enter fullscreen mode Exit fullscreen mode

You can see above that the resulting array contains all elements except the (0-based) element at index 3. We can then simply call product on the resulting array. Since we're interested in indices, we might map a sequence of indices rather than the given array itself:

scala> val len = given.length
len: Int = 5

scala> (0 until len) map { i => (given.dropRight(len-i) ++ given.drop(i+1)).product } 
res29: scala.collection.immutable.IndexedSeq[Int] = Vector(120, 60, 40, 30, 24)
Enter fullscreen mode Exit fullscreen mode

This is still a bit unwieldy (though it does avoid division, as requested in the prompt). And it requires us to traverse the array many times, create smaller arrays, then traverse those arrays. A better way of doing this might be to calculate the product of all of the elements first, then simply divide the product by the nth element to get the value of the new array at index n:

scala> val prod = given.product
prod: Int = 120

scala> given.map(e => prod / e)
res30: Array[Int] = Array(120, 60, 40, 30, 24)
Enter fullscreen mode Exit fullscreen mode

This is much cleaner, and only requires two traversals of the given array. Packaged into a method with a similar signature as the Java version of my solution, this might look like:

scala> :paste
// Entering paste mode (ctrl-D to finish)

def codingProblem002 (given: Array[Int]): Array[Int] = {
  val prod = given.product
  given.map(e => prod / e)
}

// Exiting paste mode, now interpreting.

codingProblem002: (given: Array[Int])Array[Int]

scala> codingProblem002(Array(1, 2, 3, 4, 5))
res31: Array[Int] = Array(120, 60, 40, 30, 24)
Enter fullscreen mode Exit fullscreen mode

That's it! Note that the explicit type annotation on the method (: Array[Int]) isn't strictly necessary, but it can be useful for humans reading -- and trying to reason about -- this code in the future.

Discussion

This problem gives, I think, a great contrast between the imperative, Java-like way of solving a problem like this, and the functional, Scala-like way. The Scala code is about 5x shorter, takes less mental overhead to interpret, is less prone to bugs, and more.

Can you come up with a shorter (or more performant, or more legible) way to solve this problem? I'd love to see it!


All the code for my Daily Coding Problems solutions is available at github.com/awwsmm/daily.

Suggestions? Let me know in the comments.

If you enjoyed this post, please consider supporting my work by buying me a coffee!

Discussion (3)

pic
Editor guide
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 }
    }

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)
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.