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

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)