# Product of all elements inside array except current

.

Bonjour Malick

I failed my last 3 coding interviews. It's not that I was not able to pass them. I think I'm starting to forget the fundamentals. If I want to continue in this profession, I need to go over my lessons and maybe start Leetcode as a daily routine. Let's play some music shall we?

# 0.

I will try to write my chain of thoughts.

# 1. The statement:

``````Given an array nums, of n integers,
write a program to return an array product such that
product[i] is equal to the product of all the elements of nums
except nums[i].

The product of any prefix or suffix of nums
is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n),
without using the division operation...

Given an array nums of n of integers where n > 1,
return an array output such that output[i] is equal to
the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]
Constraint: It's guaranteed that the product of the elements
of any prefix or suffix of the array (including the whole array)
fits in a 32 bit integer.

Note:
- Solve it without using the division operator
- Write a program that runs in O(n) time.

Could you solve it with constant space complexity?
The output array does not count as extra space
for the purpose of space complexity analysis.
``````

# 2. First attempt, write something:

I decided to write a program without respecting the whole statement. I first tried to write something, I first tried to write anything that could give me the desired result.

• multiply all the items inside the array
• divide by the current item, unless this item equals zero
• store the result inside another array
• return the array
``````def d(nums: list[int]) -> list[int]:
product = []

# go through all the items
for i in nums:
m = 1
# if current item not equals zero
if i != 0:
# multiply all the items
for j in nums:
m *= j
# divide by current item
product.append(m // i)
# if current item equals zero
else:
# multiply all the items except the current one
for j in nums:
if j != i:
m *= j
# no need to divide, we can't divide by zero
# plus, the item was already excluded when multiplying
product.append(m)
return product
``````

# 2. Second attempt, remove the division operator:

There are 2 problems with my solution: the program use the division operator and the program does runs in O(n²) time. Let's try to get rid of the division operator (it sounds like the easiest thing to do):

``````def e(nums: list[int]) -> list[int]:
product = []

# go through all the items
for i in nums:
m = 1
# if current item not equals zero
if i != 0:
# multiply all the items
for j in nums:
m *= j
# divide by current item but without using division
k = 0
m += i
while m > i:
m -= i
k += 1
product.append(k)
# if current item equals zero
else:
# multiply all the items except the current one
for j in nums:
if j != i:
m *= j
# no need to divide, we can't divide by zero
# plus, the item was already excluded when multiplying
product.append(m)
return product
``````

# 3. Third attempt, remove the division operator, again:

I've managed to get rid of the division operator. But I have introduced another loop within the program. This will worsen the performance. If I try to compare execution time, this is what I have:

``````# let's try to measure execution time for our 2 functions
# by using the timeit function from the timeit module
t = timeit(lambda: d([1, 2, 3, 4]))
print(t) # ~0.7731416939059272

t = timeit(lambda: e([1, 2, 3, 4]))
print(t) # ~2.5302764819934964, slower
``````

## 3.1. Let's try another idea:

• go through all the items in the array
• and for each item, again go through all the in items in the array (except the current one)
• multiply them
``````def f(nums: list[int]) -> list[int]:
# get length of the array
length = len(nums)
# create the array containing the products
product =  * length
for i in range(length):
for j in range(length):
# condition for skipping the current item
if j == i:
continue
product[i] = product[i] * nums[j]
return result
``````

This program is not yet running in O(n) time, but, there is some progress:

• not using the division operator.
• already running faster than the previous function (~1.3750199479982257 on my machine)

## 3.2. Finally noticing a pattern:

What the previous function is doing can be broken down to:

• multiplying everything that is on the left of the current item: prefix
• multiplying everythint that is on the right of the current item: suffix
• multiplying prefix and suffix
``````[X, 2, 3, 4] # prefix items: none,      suffix items: [2, 3, 4]
[1, X, 3, 4] # prefix items:  ,      suffix items: [3, 4]
[1, 2, X, 4] # prefix items: [1, 2],    suffix items: 
[1, 2, 3, X] # prefix items: [1, 2, 3], suffix items: none
`````` # 5. Fourth attempt, prefix and suffix:

``````The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
``````

The statement was really trying to give me a clue and I did not pay enough attention. The prefix of nums really meant: `the product of all the numbers to the left of the current index`. And the suffix of nums reall meant: `the product of all the numbers to the right of the current index`.

## 5.1. the product of all the numbers to the left of the current index:

``````def g(nums: list[int]) -> list[int]:
length = len(nums)
product =  * length
prefix = 1
for i in range(length):
product[i] = prefix
prefix *= nums[i]
return product
``````

## 5.2. the product of all the numbers to the right of the current index:

``````def h(nums: list[int]) -> list[int]:
length = len(nums)
product =  * length
suffix = 1
for i in range(-1, -1 * (length + 1), -1):
product[i] *= suffix
suffix *= nums[i]
return product
``````

# 10. While I still have your attention:

Join us as we make history with the first-ever DjangoCon Africa 2023 that will be held at the State University of Zanzibar Tanzania, from 6th - 11th November 2023. 