 # Code Challenge #15: July 19, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reported to have been asked in interviews at Google:

### Basic Difficulty

Write a function, `productOfTheOthers` that, when given an array of `n` integers, replaces each number in the array with the product of all the numbers in the array except the number itself.

• for example, when given the array `[1,2,3,4]`, `productOfTheOthers` would return `[24, 12, 8, 6]`
• Function Name: `productOfTheOthers`
• Input: an array – for your submission use the test array `[3, 9, 7, -2]`
• Output: an array – when given the test array, your submission should return `[-126, -42, -54, 189]`
• Example: `productOfTheOthers([3, 9, 7, -2]) => [-126, -42, -54, 189]`
• Your array may have `n` integers, presume that `n > 1`.
• Would your function work if the input array contained zeroes?

### Intermediate difficulty

Solve the basic challenge, but this time do so without using division. Call this new function `advProductOfTheOthers`.

• Function Name: `advProductOfTheOthers`
• Input: an array – for your submission use the test array `[0, 9, 7, 8, -2]`
• Output: an array
• Example: `advProductOfTheOthers([1,2,3,4]) => [24, 12, 8, 6]`

### Hard Difficulty

Write `advProductOfTheOthers` as efficiently as possible.

#### `Reply` to this thread with a link to your code on repl.itand paste your properly formatted code to participate! Don’t just submit your code, remember to `explain` your solution, too! If you want to be considered as the winner, your function `must` have the `correct name` and provide `output in the format specified` above, you also need to abide by our other simple rules.

As always solutions using imports to do all the heavy lifting such as `itertools` will not be considered for the winner.

The fine print:

``````def advProductOfTheOthers(arr)
store = []                 #An empty array that we will store our desired output in
trash = []                 # A placeholder array that will temporaily store integers from the args array
arr.reject! {|n| n == 0} #Removes zeroes (not sure if that's what is intended by challenger)
(arr.length).times {      # Avoids looping, We only execute the code as necessary for the instructions
trash << arr.shift       # Take out the first integer
store << arr.inject(:*)  # multiply the product of others and save it in the store array
arr.push(trash.pop)      # give the args array its integer back and start over as necessary
}
return store
end

``````

A quick hack that I had fun with, initially I had some crazy loops and tons of << going on. I feel pretty good about its “elegance” it feels ruby like.

Reject any zeroes in the Array
trash “holds” our number via a shift from arr
store holds the value of (the product of the others)
push the “trash” number to the back to its original array
shift over the second number to trash…
Repeat arr.length times (Until every number has been in trash and all “other products” have been stored in store
return store

The line that rejects zeroes can easily be commented out if it isn’t working as intended per the challenge.

Here’s how I did it, using Python 3. Since I didn’t use division, I guess I kind of did the basic and intermediate difficulty on the same attempt… My disappointment with this is the time complexity, since it uses a nested loop inside a loop the time complexity is terrible Here’s the link to repl.it: https://repl.it/J9Ht/11

``````def advProductOfTheOthers(num_array):
product = 1 #start the variable to hold the product of all numbers \
#except the number itself
product_list = [] #final list to hold the values of each product
for i in range(0,len(num_array)): #loop though num_array
for n in num_array: #for each number in num_array
#if n is different from the current number of number (i), \
#then multiply it by product, else it is ignored
if n != num_array[i]:
product *= n
product_list.append(product) #add product to the product_list list
product = 1  #restart the product variable
return product_list

``````
2 Likes

Hard Difficulty, Ruby

``````def advProductOfTheOthers(array)
array.map do |number|
array.select { |n| n != number }.inject(&:*)
end
end

``````

Edit: To add an explanation- I used map in order to return an altered array, rather than each which returns the array iterated over. select and the accompanying block returns an array of every element of the original array except for the element currently being dealt with. inject called with * as a method then multiplies together all elements of the array returned by select, returning an integer, which takes the place of the original element in the array.

2 Likes

``````function advProductOfTheOthers(input) {
let product = 1,
output = [];

for(let i = 0; i < input.length; i++) {
for(let j = 0; j < input.length; j++) {
if(input[i] !== input[j]) {
product *= input[j];
}
}

output.push(product);
product = 1;
}

return output;
}

``````

Not sure how to make this more efficient than it is. Got a feeling two loops is probably not the best method.

2 Likes

Ruby solution

``````def productOfOthers(arr)
result = []
(0).upto(arr.count - 1) do |x|
result << arr.reject { |y| y == arr[x] }.inject(:*)
end
result
end

``````

Runnable code : https://repl.it/J9XY

1 Like

``````function advProductOfTheOthers(input) {
product = 1;
output = [];

for(var i = 0; i < input.length; i++) {
if (input[i] !== 0){
product *= input[i];
}else {
return ("...ZERO...");
}
}
for(var j = 0; j < input.length; j++) {
output[j] = product / input[j];
}
return output;
}
``````

Intermediate in Python3

``````def advProductOfTheOthers(inarray):
outarray = []
index = 0
subindex = 0

while index < len(inarray):
product = 1
while subindex < len(inarray):
if subindex != index:
product *= inarray[subindex]
subindex += 1

outarray.append(product)
index += 1
subindex = 0

return outarray

``````

Justification:
I create the outarray from the get go. Initialize some vars to retain index and subindex (for the current position in the array and then the position to multiply the current index by) and then iterate through those indexes, comparing if the index is the same as the subindex, and if it is, just ignore.

Hard Difficulty in Java: https://repl.it/J9kZ/3

``````public static int[] advProductOfTheOthers(int[] n) {

int[] n_ = new int[n.length]; //To save the response.
int Product = 1;

//Get the product of all numbers that are before the current number.
for(int i=0; i<n.length; i++) {
//Consider the first number as a special case.
if (i!=0) {
n_[i] = Product;
} else {
n_[i] = 1;
}
Product *= n[i];
}

//Get the product of all numbers that are after the current number.
Product = 1;
for(int i=n.length-1; i>=0; i--) {
//Consider the last number as a special case.
if (i!=n.length-1) {
n_[i] *= Product;
}
Product *= n[i];
}

return n_;
}
``````

The complexity of this solution is O(n). The trick is that you can calculate first the product of all the numbers that to the left of the current number in one past. After that, you can calculate the product of all the numbers that to the right of the current number, also in one pass. If you do a simple multiplication like productOfTheNumberToTheLeft * productOfTheNumberToTheRight, you will get the correct answer. Another important think to have in mind is that the lines `Product *= n[i];` are the ones that help you to alway have the updated product of all the number to the left or to the right of the current number.

Note: the solution does not work if the imput have a zero (or several). It would be easy to program workarounds like removing any zeros or replace them by 1s. All needed is to put another `for` at the start to do the cleanup.

5 Likes

JavaScript - Basic Challenge
To solve the basic requirement I initially sought to find the actual total product of the array then use that value to map a new array dividing out the values in turn.

https://repl.it/J9ql/0

``````function productOfTheOthers(arr) {
"use strict";
// First find the product of all of the elements in the array
const totalProduct = arr.reduce((accum, next) => {
return accum * next;
});

// Then return an array with each value divided from totalProduct
return arr.map(num => totalProduct / num);
}

const testData = [3, 9, 7, -2];

console.log(productOfTheOthers(testData));
``````

This ends up going over the data set twice making it O(2n) or just O(n). (Am I understanding that right?)

@danieloduffy how would you like zeros to affect the output? If there’s a single zero then the only non-zero value in the output array would be the index of the zero value. Is this the desired result or would you have us remove any zeros from the array at the outset?

2 Likes

Hey, that’s my Basic Difficulty challenge in Python3!
It would be nice if someone could give me a feedback about my code Code: 1 Like

Solution in PHP

``````function productOfTheOthers(\$input){
\$final = [];
\$size = count(\$input);
for(\$key = 0; \$key < \$size; \$key++){
\$product = 1;
for(\$i = 0; \$i < \$size; \$i++){
if(\$i != \$key && \$input[\$i] != 0){
\$product *= \$input[\$i];
}
}
array_push(\$final, \$product);
unset(\$temp);
}
print_r(\$final);
}

productOfTheOthers([3, 9, 7, -2]);
``````

I think you could speed it up a tiny bit by skipping the value to be replaced with an if statement.

Also, I wonder if there’s a way to take advantage of an array that has a zero in it–you could check and then short circut your code to replace everything that’s not zero with a zero.

My solution:

``````function productOfOthers(arr) {
var result = [], prod;
arr.forEach(function(num, i, a) {
prod = a.reduce(function(acc, el) {
return el === arr[i] ? acc : acc * el;
}, 1);
result.push(prod);
});
return result;
}
``````

Yeah I don’t have the zero handling yet because I was waiting on finding out whether they wanted the zeros in or filtered out. At the moment I believe it produces `NaN` for zero values.

JavaScript - Intermediate/Hard

https://repl.it/JaEG/1

``````function advProductOfTheOthers(arr) {
"use strict";
const tree = getProductTree(arr),
products = [];

for (let i = 0, l = arr.length; i < l; i++) {
let prod = 1;
let local = i;
for (let j = 0, k = tree.length; j < k; j++) {
const other = local % 2 ? tree[j][local - 1] : tree[j][local + 1];
prod *= typeof other === "undefined" ? 1 : other;
local = Math.trunc(local / 2);
}
products.push(prod);
}
return products;
}

// The below helper function creates a tree by multiplying the values
// in pairs. Given the provided test set of [0, 9, 7, 8, -2]
// The output is an array whose entries are:
// [0, 9, 7, 8, -2]
// [0, 56, -2]
// [0, -2]
// This data structure allows me to avoid multiplying any 2 values more
// than once.

function getProductTree(arr) {
"use strict";
const tree = [arr];
while (tree[tree.length - 1].length > 2) {
const branch = [],
leaves = tree[tree.length - 1];

for (let i = 0, l = leaves.length; i < l; i++) {
if (i % 2) {
branch.push(leaves[i] * leaves[i - 1]);
} else if (i === l - 1) {
branch.push(leaves[i]);
}
}
tree.push(branch);
}
return tree;
}
``````

Explanation to be given in an hour or so, my son just woke up from his nap and its beautiful outside. EDIT - How my code works: this challenge reminded me of Douglas Crockford’s recursion example in Good Parts where he memoizes previous fibonacci additions to limit the number of recursive calls. My goal became solving the challenge without multiplying the same two numbers twice.

I had recently watched a video by Anjana Vakil about JS Data Structures where she was able to navigate a tree to isolate values. Though the video itself is more about mutable data, the way she explained the traversal of the tree made more sense to me than many other articles I’ve read. I figured it wouldn’t be too hard to generate a similar structure and take everything BUT the element I was looking for. (it actually was quite difficult)

The function `getProductTree` does this, returning an array of arrays where every element is a folded version of two numbers multiplied from the previous array. This allows me to selectively multiply values local to the current value and then multiply larger cached values as needed. I was reminded of the many dream levels in Inception.

By working on a tree of products I was able to achieve the requirement of never dividing (as long as you don’t count slashing my iterators…) and achieving the desired result. This solution just naturally handled 0’s well so, yeah, I liked it.

One thing that I found myself wishing for was a more natural way to retrieve the last element of an array. There is already a `array.length` property, why can’t we have an `array.last` pointer?

3 Likes

Basic/Intermediate

Currently thinking about a hard solution. Maybe some sort of tree or graph for storing sub parts of the multiplication

``````from typing import List

def productOfTheOthers(input_list: List[int]) -> List[int]:

zero_count = input_list.count(0)

if zero_count > 1:
return  * len(input_list)

# In case of a single zero, all products but the index of the zero value will be zero.
elif zero_count == 1:
product = 1

for integer in input_list:
if integer == 0:
continue

product *= integer

return_list =  * len(input_list)
return_list[input_list.index(0)] = product

return return_list

# In case of no zeroes, we calculate the total product
else:
product = 1

for integer in input_list:
product *= integer

# When generating the return list, we divide the product by each int in the input list to
# subtract it from the equation.
return [int(product / integer) for integer in input_list]

# Here it would be easy to add the 'zero handling' of the first solution, but I decided to keep it
# clean so it's easier to work with, for the hard solution

def product_of_the_others(current_index):

product = 1

for index, value in enumerate(input_list):

if index == current_index:
continue

product *= value

return product

return [product_of_the_others(index) for index in range(len(input_list))]

if __name__ == '__main__':
print(productOfTheOthers([0, 3, 9, 7, -2, 0]))
print(productOfTheOthers([0, 3, 9, 7, -2]))
print(productOfTheOthers([3, 9, 7, -2]))

``````

I guess this is solution for Hard, with O(n log n)
https://repl.it/Jbmx

Description:
A function call that take in a arr and a constant (default value 1), always break the input array into 2 array, left and right, and perform recursive call, just multiply input constant with all number in left/right array to be the constant for the recursive function call for right/left array.

``````def productOfTheOthers(arr, k=None):
if k == None:
k=1
size=len(arr)
if size == 1:
return [k]
else:
larr = arr[:size/2]
rarr = arr[size/2:]

kr=k
for i in larr:
kr = kr*i

kl=k
for i in rarr:
kl = kl*i

return productOfTheOthers(larr,kl) + productOfTheOthers(rarr,kr)

print productOfTheOthers([3, 9, 7, -2])
``````

Solution 2, should be hard I think, O(2n)
https://repl.it/Jbp2/3

``````def productOfTheOthers(arr):

s=len(arr)
r = []

# Create an array of size with value
#  = all number multiplied on the left
k=1
for i in range(s):
r += [k]
k *= arr[i]

# multiply with all number  on the right
k=1
for i in reversed(range(s)):
r[i]*=k
k   *= arr[i]

return r

print productOfTheOthers([3, 9, 7, -2])
``````
3 Likes

Intermediate difficulty JavaScript

``````function advProductOfTheOthers(arr){
var newArr = [];
for (n=0; n<arr.length; n++){
// first I duplicate the original array
var myArr = arr.concat();
// then I used splice method to remove array element so it won't be used for product
myArr.splice(n,1);
var pro = myArr;
for (i=1; i<myArr.length; i++){
pro *= myArr[i];
}
// after loop, product is added to new array
newArr.push(pro);
}
return newArr;
}

``````

Having been recently exposed to dynamic programming, my first idea for hard level solution involved an exuberant recursive function with a memoizing decorator. But it was the time to go jogging and clear my mind, and the idea for the code has soon become much clearer as well.

Consider an array `[1,2,3,4,5,6,7,8,9].` To compute a product of everything else than say 4, we need to multiply products of everything to the left of 4 (arrays index 3 in this case) and everything to the right of it:
`prod([1,2,3]) * prod([5,6,7,8,9])`
Now notice the left-of-4 product of [1,2,3] is a product of left-of-3 * the value 3 itself:
`prod([1,2]) * 3`
Similarily, on the other side:
`prod([5,6,7,8,9]) = 5 * prod([6,7,8,9])`
Meaning, rather than computing each product by brute force, we can start from each end of the array and compute left-of and right-of products using previously calculated values, not unlike most people would compute Fibonacci numbers. This is what my function does in the first loop, populating the `p` cache with values at positive keys for left-of-i products and negative keys for right-of-i ones (eg. for 4 in `[1,2,3,4,5,6,7,8,9]` the keys would be 3 and -6, both reflecting the index of 4 in the array). Once it’s done, we get our everything-but product by multiplying left-of-i and right-of-i pair for each i.

``````def advProductOfTheOthers(arr):
p = {0:1, -1:1}   # products ([:i] for pos. keys, [i:]-neg. keys)
n = len(arr)
for i in range(1,n):
p[i]    = arr[i-1] * p[i-1]  # prod of elements left of i
p[-i-1] = arr[-i]  * p[-i]   # prod of elements right of i
return [p[i]*p[-n+i] for i in range(n)]
``````

The code completes within 2 iterations, executing 3*n multiplications. Everything else is writing to / reading from the dictionary. Didn’t bother to figure out the possibility of creating the dictionary cache with list comprehension, because while probably faster, it would muddle the core of the code, and readability counts.

I’ve made no arrangements for presence of 0’s as these are sort of uninvited guests to a product-computing routine. Should these be expected in the input array though, code should include an `if` statement to short-circuit at the first occurence and only compute its everything-else-but product - values for all other array elements will be 0.

Code running at repl.it.

4 Likes