Product Of Other Numbers

Problem:

You have a list of integers, and for each index you want to find the product of every integer except the integer at that index.

Restrictions: divisions are not allowed.

First thought that comes to my mind is to use 2 for-loops and multiply all the indices except the current one of the first loop. Easy, finished in less than a minute. The issue is the solution has an n^2 complexity.

How to optimize?

As usual the problem is the data is not organized in a nice way for this problem. Time to analyze!

Given an example:

input: [1,2,3,4]
expected output: [24, 12, 8, 6]
output expanded: [2*3*4, 1*3*4, 1*2*4, 1*2*3]

By looking at the expanded output, I can see there is a pattern going on. Exactly what it is took me a few minutes to figure it out, but right out of the box I can definitely see that:

The lowest index of the input is added on the expanded output with an index of 1. In other words the number 1, with an index 0, of the input array, was added on the index 1 of the output array; which makes sense given that index 0 of the input cannot be considered in the product of the output in index 0.

Note: this sort of reminds me to the fibonacci problem were you have to reuse operations to avoid recalculating the same thing over and over. Its hard to think how to reuse operations though. In this case I have to break it into sub-problems to identify the patterns.

A few minutes pass of me staring at the whiteboard and I realize that the current index has all the numbers to the left and to the right of it.

index 2 of ouput expanded: [—,—,1*2*4,—]

The 1 and 2 are numbers to the left of the current number and 4 is to the right. Sounds silly, but that helps to think about the solution. In other words, the current number is the product of all the numbers to the left and all the numbers to the right!

What if I have 2 extra arrays:

  • before[] where its current index is the product of all the indices before it.
  • after[] where its current index is the product of all the indices before it.

I can then loop through the before[] and after[] array and simply multiply the current index and store it in a result[] array.

I am not sure, but that sounds like it reduces the complexity (hopefully to 2 individual loops).

It sounds like a good moment to start drawing some code (I say drawing because I am getting used to whiteboards so I write it there first).

My first attempt looked something like this:

public int[] getProduct(int[] numbers){
int[] result = new int[numbers.length];
int[] arrBefore = new int[numbers.length]; 
int[] arrAfter = new int[numbers.length]; 
int productBefore = 1;
int productAfter = 1; 
int b = numbers.length - 1; 

//Organize the data 
for(int a = 0; a < numbers.length; a++){
productBefore *= numbers[a];
productAfter *= numbers[b];
arrBefore[a] = productBefore;
arrAfter[b] = productAfter;
 b--; 
} 

//Calculate the result 
for(int a = 0; a < numbers.length; a++){ 
result[a] = arrBefore[a] * arrAfter[a]; 
}
return result;
}

I made a mistake here! I did not realize right away the ordering of the multiplication and assigning the arrays was important. First I need to assign the value to the product array, otherwise I am skipping ahead.

(I briefly made another mistake but corrected it in my mind. Initializing the product variables to 0 because there are no values before the first or last index. What is interesting is the representation of this emptiness works well with the number 1 and not 0 – also 0 would just 0 out the entire multiplication)

Small correction:

public int[] getProduct(int[] numbers){
int[] result = new int[numbers.length];
int[] arrBefore = new int[numbers.length]; 
int[] arrAfter = new int[numbers.length]; 
int productBefore = 1;
int productAfter = 1; 
int b = numbers.length - 1; 

//Organize the data 
for(int a = 0; a < numbers.length; a++){
arrBefore[a] = productBefore;
arrAfter[b] = productAfter;
productBefore *= numbers[a];
productAfter *= numbers[b];
 b--; 
} 

//Calculate the result 
for(int a = 0; a < numbers.length; a++){ 
result[a] = arrBefore[a] * arrAfter[a]; 
}
return result;
}

It works and its optimized!

  • n+n or 2n is the new processing complexity.
  • I also sacrificed some memory, 2 arrays of n or 2n memory to be exact. On the bright side we can buy more memory.

I liked this problem because it involves memoization, which I am not very good at spotting right away; my brain is not used to seeing it. Good practice!

Code available on github

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s