## CodeFights Solves It, Interview Practice Edition: productExceptSelf

If it’s been asked as an interview question at Amazon, LinkedIn, Facebook, Microsoft, AND Apple, you know it’s got to be a good one! Have you solved the challenge productExceptSelf in Interview Practice yet? If not, go give it a shot. Once you’re done, head back here. I’ll walk you through a naive solution, a better solution, and even a few ways to optimize.

…Done? Okay, let’s get into it!

The object of this problem is to calculate the value of a somewhat contrived function. The function `productExceptSelf`

is given two inputs, an array of numbers `nums`

and a modulus `m`

. It should return the sum of all **N** terms `f(nums, i)`

modulo `m`

, where:

`f(nums,i) = nums[0] * nums[1] * .... * nums[i-1] * nums[i+1] * ... * nums[N-1]`

Whew!

We can see this most easily with an example. To calculate `productExceptSelf([1,2,3,4],12)`

we would calculate:

`f([1,2,3,4], 0 ) = 2*3*4 = 24`

`f([1,2,3,4], 1 ) = 1*3*4 = 12`

`f([1,2,3,4], 2 ) = 1*2*4 = 8`

`f([1,2,3,4], 3 ) = 1*2*3 = 6`

The sum of all these numbers is `50`

, so we should return `50 % 12 = 2`

.

## A naive solution

The explanation of the code suggests an implementation:

1 2 3 4 5 6 7 8 9 10 11 12 |
# Don't use this function! def f(nums,i): ans = 1 for index, n in enumerate(nums): if index != i: ans *= n return ans def productExceptSelf(nums, m): # Add up all the results of the f(nums, i), modulo m return sum([f(nums,i) % m for i in range(len(nums))]) % m |

This is *technically* correct, but the execution time is bad. Each call to the function `f(nums, i)`

has to do a scan (and multiplication) in the array, so we know the function is `O(N)`

. We call `f(nums,i)`

a total of `N`

times, so this function is `O(N`

^{2}`)`

!

Sure enough, this function passes all the test cases. But it gives us a time length execution error on test case #16, so we have to find a more efficient solution.

## Division is a better solution (but still not good enough)

A different way of approaching this problem is to find the product of all the numbers, and then divide by the one you are leaving out. We would have to scan to see if any of the numbers were zero first, as we can run into trouble dividing by zero. Essentially, we’d have to deal with that case separately, but it turns out that any array `nums`

with a zero in it is easy to calculate. (This would be a good extension exercise!)

If we look under the constraints of the code, we are told that `1 <= nums[i]`

, so we don’t have to worry about this case. We can simplify our problem to:

1 2 3 4 5 6 7 8 9 10 |
# This version still doesn't run fast enough... # but why?? def productExceptSelf(nums, m): productAll = 1 for n in nums: productAll *= n # these are the f(nums,i) we calculated before f_i = [productAll / n for n in nums] return sum(f_i) % m |

Again, we get a time execution error! Note that the running time is much better. We make a pass through the array once to get `productAll`

, then a pass through the array again to get the `f_i`

, and one more pass through the array to do the sum. That makes this is a *O(N)* solution!

## Why is the interviewer asking this question?

In other words, what is this question testing? As I mentioned in the introduction, the function we’re calculating is a little contrived. Because it doesn’t seem to have any immediate applicability, the companies asking us this question in interviews are probably looking to see if we know a particular technique or trick.

One of the assumptions that I made when calling the algorithms `O(N)`

or `O(N`

^{2}`)`

was that multiplication was a constant time operation. This is a reasonable assumption for small numbers, but even for a computer there is a significant difference between calculating

`456 x 434`

and

`324834750321321355120958 x 934274724556120`

There are a couple of math properties of **residues** (the technical name for the “remainders” the moduli give us) that we can use. One is:

`(a + b + c ) % m`

is the same as `(a % m + b % m + c % m) % m`

This is nice because `a%m`

, `b%m`

, and `c%m`

are all small numbers, so adding them is fast.

The other property is:

`(a * b) % m`

is the same as `((a % m) * (b % m)) % m`

That is, I can multiply the remainders of `a`

and `b`

after division by `m`

, and the result I get will have the correct remainder.

At first glance, this doesn’t seem to be saving us much time because we’re doing a lot more operations. We are taking the modulus three times per multiplication, instead of just once! But it turns out that the modulus operation is *fast*. We more than make up for it by only multiplying small numbers.

So we can change our calculation of `f_i`

to

1 2 3 4 |
# same as before f_i = [(productAll / n) % m for n in nums] return sum(f_i) % m |

This still isn’t good enough to pass the test, but we’re getting there. The problems we still have are:

- The number
`productAll`

is still very large - Integer division is (relatively) slow

Our next approach will eliminate both of these problems.

**Note: NOT a property**

The big number is `productAll`

, so you might hope that we can find `productAll % m`

, and _then_ do the division. This doesn’t work.

The mathematical problem is that non-zero numbers can be multiplied to give 0, so division is problematic. Looking at division, and then taking a modulus:

`48 / 6 = 8_ so _(48 / 6) % 12 = 8`

but reversing the order (taking the modulus, then doing the division) yields:

`(48 % 12) / 6 = 0 / 6 = 0`

So we can’t take the modulus of `productAll`

and avoid big numbers altogether.

## Prefix products (aka cumulative products)

We can speed up the execution by building by an array, `prefixProduct`

, so that `prefixProduct[i]`

contains the product of the first `i-1`

numbers in `nums`

. We will leave `prefixProduct[0] = 1`

.

1 2 3 4 5 6 7 |
... ... prefixProduct = [1] * len(nums) for i in range(1,len(nums)): prefixProduct[i] = prefixProduct[i-1]*nums[i-1] ... |

The neat thing about this array is that `prefixProduct[i]`

contains the product of all elements of the array up to `i`

, not including `i`

. If we also made a `suffixProduct`

such that `suffixProduct[i]`

was equal to all the product of all numbers in `nums`

past index position `i`

, then the productExceptSelf for number `i`

would just be the product of all numbers except the i^{th} one = `prefixProduct[i] * suffixProduct[i]`

We have eliminated one of the costly operations: division! We can also avoid seeing large numbers in the multiplication as well, by changing the step inside the loop to contain a modulus.

Our new solution is:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
def productExceptSelf(nums, m): prefixProduct = [1]*len(nums) suffixProduct = [1]*len(nums) # setup the cumulative product from left and right for i in range(1,len(nums)): # Need parenthesis, as % has higher precedence than * prefixProduct[i] = (prefixProduct[i-1] * nums[i-1]) % m suffixProduct[-i-1] = (suffixProduct[-i] * nums[-i]) % m total = 0 for i in range(len(nums)): # start at the end, with prefixProduct -1 # and scan right total += (prefixProduct[i]*suffixProduct[i]) % m return total % m |

This finally works! We’ve eliminated all multiplication by big numbers (but still have multiplications by small numbers), and no divisions at all. But we can still do better…

## For the technical interview, an even better solution

It turns out that we don’t need to have a `suffixProduct`

. We can build it as we go! This is the *accumulator pattern*:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
def productExceptSelf(nums, m): prefixProduct = [1]*len(nums) suffixProduct = 1 # now this is just a number # setup the cumulative product from left and right for i in range(1,len(nums)): # Need parenthesis, as % has higher precedence than * prefixProduct[i] = (prefixProduct[i-1] * nums[i-1]) % m total = 0 for i in range(len(nums)): # start at the end, with prefixProduct -1 # and scan right total += (prefixProduct[-1 - i]*suffixProduct) % m suffixProduct = (suffixProduct * nums[-1-i]) % m # now multiply suffixProduct by the number that # was excluded return total % m |

## Takeaways

The main things you’re being asked to think about in this task are:

- Arithmetic operations aren’t always constant time. Multiplying big numbers is much slower than multiplying small numbers.
- Operations are not all the same speed. Integer modulus is
*very*fast, addition and multiplication are fast, while division is (relatively) slow. - Some number theory: You can multiply the residues of numbers, instead of the numbers themselves. But you cannot divide by residues, or divide the residues unless you have certain guarantees about divisibility.
- The idea of precomputing certain operations, which is where the
`prefixProduct`

comes in.

Other problems that use the **cumulative** or **prefix** techniques are finding the lower and upper quartiles of an array, or finding the equilibrium point of an array. (I cover prefix sums in a lot more detail in this article.)

## Footnote: Horner’s Method

One of the solutions presented used a method of calculation known as Horner’s method. Take the cubic

`f(x) = 2 x^3 + 3 x^2 + 2 x + 6`

To evaluate `f(3)`

naively would require 8 multiplications (every power `x^n`

is `n`

copies of `x`

multiplied together, and then they are multiplied by a coefficient), and three additions. There is a lot of wasted calculation here, because when we calculate `x^3`

we calculate `x^2`

in the process! We could store the powers of `x`

separately to reduce the number of multiplications.

Horner’s method is a way of doing this without using additional storage. The idea is, for example, that we can use operator precedence to store numbers for us:

`3 x^2 + 2 x + 6 = (3 * x + 2) * x + 6`

The left side has a (naive) count of 4 multiplications and 2 additions, while the right side has 2 multiplications and 2 additions. Moving to the cubic is even more dramatic:

`f(x) = 2 x^3 + 3x^2 + 2 x + 6 = ( (2 * x + 3) * x + 2 ) * x + 6`

This takes our 8 multiplications and 3 additions to only 3 multiplications and 3 additions!

The shortest solution so far, submitted by CodeFighter k_lee, uses Horner’s method, along with taking moduli at the different steps. See if you can decipher it.

1 2 3 4 5 6 7 8 |
def productExceptSelf(nums, m): p = 1 g = 0 for x in nums: g = (g * x + p) % m p = (p * x) % m return g |

## Tell us…

Did your solution for this Interview Practice challenge look different than mine? How did you approach the problem? Let us know over on the CodeFights forum!