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 ati
.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 n
th 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!
Top comments (3)
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
: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.