Daily Coding Problem: Problem #2

Daily Coding Problem: Problem #2
0

#1

If you are wondering what’s this thing? Then before continuing, please read this.

Problem #2

This problem was asked by Uber.

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 at i .

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?


Solve. Discuss. Repeat. Happy Coding!


#2

I would think a filter and then a reduce function would do the job.


#3

Here’s what I got for JS

// original
const productArray = arr => [...arr].map(n =>(
    arr.reduce((a,c)=> a*c)/n
));

// with no division
const productArray = arr => [...arr].map((_,i) =>(
    arr.filter((_, j) => i !== j)
       .reduce((a,c)=> a*c)
));

#4
// who needs division when you dont have higher order function

findProductOfIntegers = (numbers) => { 
  let productArr = [];
  for(let number in numbers){
    let total = 1;
    let skippedIndex = number;
    for(let i = 0; i < numbers.length; i++) {
      if(skippedIndex != i) {
        total = numbers[i] * total  
      }        
    }
    productArr.push(total)
  }
  return productArr
}

#5

My solution attempt.

<script>
    const inputArr = [1, 2, 3, 4, 5];
    

    const productOfArrayElements = (inputArr) => {
      let value;
      let tempArr = [];
      let productArr = [];
      
      for (let i = 0; i < inputArr.length; i++) {
          tempArr = inputArr.slice(0); //Set temp array to input array's values.
          tempArr.splice(i,1); //Remove the current element.
          value = tempArr.reduce(getProduct); //Find the product of all other elements.
          productArr.push(value); //Add product value to the product array.
      }

        return productArr;
    }


    const getProduct = (total, num) => {
       return total * num;
    }

    console.log(productOfArrayElements(inputArr));
  
  </script>

#6

For my solution:

First I wrote it out by hand (no loops) for an array of three integers, to get my head around the goal. In Big O, I think my solution is exponential?

function arrayOfProducts(array){
    let allButIndex = [];
	let result = [];
	for(let i = 0; i < array.length; i++) {
		// i need to get every element that is not the current one. push. push.
		allButIndex = [];
		for(let j = 0; j < array.length; j++) {
			if (j != i) {
				allButIndex.push(array[j]);
			}
		}
		result[i] = allButIndex.reduce((a, b) => a * b);
	}
	return result;
}

#7

Possible Js solutions

// With divison
function productExceptMe(arr){
	return arr.map((num) => arr.reduce((x,y) => x*y)/num);
}

// without divison
function prouctExceptMe(arr){
	var newArr = [];
	for(let i=0;i<arr.length;i++){
		var n = arr.splice(i,1);
		newArr.push(arr.reduce((x,y) => x*y));
		arr.unshift(...n);
	}
	return newArr;
}

#8

Looks like more than an attempt to me. That splice move is really clever. Nice!

Also I notice your code separates getProduct–is this in order to follow good design practice, or just because it was easier to conceptualize as you wrote it?

I’ve heard that we should divide responsibilities between functions every time you say the word “and” when describing what it does. How do you (and anybody in this thread) feel about that in the context of coding challenges like this?


#9

@shodak It looks quadratic to me. Because we are running over the loop of n elements twice. So, n * n = n².


#10

Thanks, zitgost! I’m sure it could be more optimized, but this way I could do it in one loop so I was happy with that.

I’m generally not a big syntactic sugar developer. If I can write code out and separate functions I will because it is easier to conceptualize and read. Being an older programmer now I find it is much easier that way when I have to look at something I wrote a few months ago…or a week. :grinning:


#11

Nice thread idea :slight_smile:

function products(arr) {
	const product = arr.reduce((a, c) => a * c);
	return arr.map((e) => product / e);
}

Without division:

function products(arr) {
	const product = arr.reduce((a, c) => a * c);
	return arr.map((e) => {
		let count = 0;
		for (let i = product; i > 0; i-=e) {
			count++;
		}
		return count;
	})
}