[Challenge] Product of Everything Else

challenge

#1

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?
Find out more about basic challenges.

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]
Find out more about intermediate challenges.

Hard Difficulty

Write advProductOfTheOthers as efficiently as possible.

Find out more about hard challenges and Big O

Reply to this thread with a link to your code on repl.it and 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:

Click the links to find out more about:


Essential Information on Code Challenges
#2

Advanced Difficulty Ruby
Repl.it link

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.


#3

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 :frowning:
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

print('advProductOfTheOthers([3, 9, 7, -2]) =>', advProductOfTheOthers([3, 9, 7, -2]))
print('advProductOfTheOthers([1,2,3,4]) =>', advProductOfTheOthers([1,2,3,4]))

#4

Hard Difficulty, Ruby
Repl.it link

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

advProductOfTheOthers([0, 9, 7, 8, -2])

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.


#5

Intermediate difficulty Javascript. JSBin link

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;
}

console.log(advProductOfTheOthers([1,2,3,4]));
console.log(advProductOfTheOthers([3, 9, 7, -2]));

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


#6

Advance difficulty
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


#7

Basic difficulty, Javascript Pepl.it link

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;
}
console.log(advProductOfTheOthers([1,2,3,4]));
console.log(advProductOfTheOthers([3, 9, 7, -2]));

#9

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
  
print(advProductOfTheOthers([0, 9, 7, 8, -2]))

Repl Link: https://repl.it/J9gc/1

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.


#10

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.


#11

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?


#13

Hey, that's my Basic Difficulty challenge in Python3!
It would be nice if someone could give me a feedback about my code :grin:
link: https://repl.it/JaTo/5

Code:


#14

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]);

#17

Nice answer!
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;
}

#18

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.


#19

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. :slight_smile:

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?


#20

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)

    # In case of two or more zeros, all products will be zero, as all products will be multiplied by 0
    if zero_count > 1:
        return [0] * 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 = [0] * 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]


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

    # 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]))

    print(advProductOfTheOthers([0, 9, 7, 8, -2]))

#22

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])

#23

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])

#24

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[0];
    for (i=1; i<myArr.length; i++){
      pro *= myArr[i];
    }
    // after loop, product is added to new array
    newArr.push(pro);
  }
  return newArr;
}

advProductOfTheOthers([0, 9, 7, 8, -2]);

#25

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.