# Daily coding problem #2

## Problem Statement

The guy at DCP send you daily problem to solve asked by top company interview, here is 2nd Problem

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?

## Approach

So let’s take brute force approach and multiply every number in the array by running an outer and inner loop except index of the outer and inner loop is equal

```
class Solution:
@staticmethod
def dcp2(nums):
if(len(nums) == 1):
return nums
result = [0]*len(nums)
for i in range(len(nums)):
new_value = 1;
for j in range(len(nums)):
new_value *= nums[j] if i != j else 1
result[i] = new_value
return result;
```

As you can clearly see that we are using two loops here and so our program time complexity is O(n^{2})

So let’s optimize our method for O(n) time complexity

- To get such multiplication at the index we need to (multiple of all number of left i) * (multiple of all number of right of i)
- To keep track of multiplication till left and multiplication till right we will use an extra space

## Time for Code

```
class Solution:
@staticmethod
def dcp2(nums):
if(len(nums) == 1):
return nums
left_multiply = [1]
right_multiply = [1]
num_length = len(nums)
for i in range(1, num_length):
left_multiply.append(left_multiply[i-1]*nums[i-1])
right_multiply.append(right_multiply[i-1]*nums[num_length-i])
right_multiply = right_multiply[::-1]
for i in range(num_length):
nums[i] = left_multiply[i] * right_multiply[i]
return(nums)
```