# Daily Coding Problem #2

### Ivan Nov 25 '18 ・1 min read

Seeing the first post gained some popularity, here is the second problem

For quite some time I found my time procastinating after getting home from work. Untill a few days ago I stumbled upon the Daily Coding Problem (DCP) and decided to give it a shot.

The code is in C#.

## How it works?

The folks at DCP send you a problem that was asked at a top company everyday for you to solve. The premium membership also offers the opportunity to verify your solution.

# 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?

# My solution

```
using System;
using System.Linq;
namespace Task02
{
public class Program
{
public static void Main(string[] args)
{
var input = Console.ReadLine()
.Split(' ')
.Select(int.Parse)
.ToArray();
var result = new int[input.Length];
for (int i = 0; i < result.Length; i++)
{
result[i] = 1;
for (int j = 0; j < result.Length; j++)
{
if (j != i)
{
result[i] *= input[j];
}
}
}
Console.WriteLine(string.Join(' ', result));
}
}
}
```

# Explanation

Here I could not think of any better than the naive solution, which works in O(n^{2)} time and you never like square complexity.

Basically for every item in the result array, foreach the input array and check if the index is different from the item's. If they are, multiply the current value of the item times the current input item

I will try to do the daily problem everyday, but sometimes life gets in the way :)

Solutions are posted in my github account

# DailyCodingProblem

This repository contains solutions of the Daily Coding Problem tasks

.

Feel free to leave a like and let me know in the comments if I should continue to post my solutions.

If you also have any better solution in mind, by all means share it, so we can learn from each other.

In python 2.7, no division, O(n) time. The tradeoff is using a bunch of memory, if the list is very long.

Or this.

Or with no additional space required:

Nice find :-)

For the first problem I'd loop over the array twice. The first time to compute the total product and the second time to fill in the output array, dividing out each element of the input array from the total product for the corresponding output element.

I'm guessing that your solution is for the follow-up question though :-). If you have logarithms you could use them to convert multiplication and division to addition and subtraction. This is a common trick when working over finite fields.

stackblitz.com/edit/js-xqagwj

I did something very similar to this. I realised quickly that if any of the numbers in the array are repeated, the totals don’t come out right. I had to explicitly remove the element from the input array and then use the reduce function to calculate the product.

HTH

Here's my TypeScript version.

This approach works in O(n) by dividing the product of all elements by

`x[i]`

.O(n) with division, in C#

Solution in Python without division, still in O(n²), but inner loop is only executed n²/2 times:

JavaScript O(n) but with division:

Here is

`O(N)`

without division:The idea is to calculate opposite partial products and then reduce them. In a language that has a proper

`map_reduce`

function implemented on enumerables (like Elixir,) that might be done in one step without intermediate variables.Simple Rust solution:

For follow-up question:

Without being aware of possible constraints on the input numbers, a solution with division is most efficient as it conserves both memory (2 array allocations: input and output) and cpu (2 enumerations of the the array, O(2n) ~= O(n)). This was described by @severinson . Here it is in F#.

To consider a solution without division, understand that we are using division here to reverse a multiplication. An alternative is to choose not to multiply in the first place. But in order to do that, we move to an O( n

^{2}) solution where we shape each element of the output array as we process the input. Then we can choose to selectively skip multiplication.Note: This function is "pure", despite using mutation internally.Part 2 solution, slightly better than O(n

^{2),}using a copy to initialize the array, and the inner loop runs 2 fewer times than the outer.Don't know if the use of Parallel.ForEach is

legit, but here's my take using C# and LinqJavascript solution, no division, O(n) time.

The idea is basically two steps:

I also do a 3rd step to map from that object to the subproducts, but that could be spared if we created a new array during step 1, but still that step would still keep it O(n)

I like the idea, I will be joining it daily. Thanks!