Scala Daily Coding Problem #002

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

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

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

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

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

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

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)

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)

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)

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!