Scala Daily Coding Problem #002
Tags: scala, challenge, beginners, dailycodingproblem
Published: 2020-03-08 16:50:39

[Daily Coding Problem](https://dailycodingproblem.com/) 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!](https://dev.to/awwsmm/java-daily-coding-problem-002-56j0)

### Code

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

```java
  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

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

```java
    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

```scala
  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:

```scala
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
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
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 `n`th element to get the value of the new array at index `n`:

```scala
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
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](https://github.com/awwsmm/daily).

Suggestions? Let me know in the comments.

If you enjoyed this post, please consider supporting my work by <a href='https://ko-fi.com/Z8Z811E9B'>buying me a coffee</a>!