CODEWITHSUNDEEP
pythonlistfor-looptime-complexitybig-o
Dishant Mewada
Dishant Mewada

Reputation: 87

Is there a way to further reduce ''the for loop'' in this python code?

I want to make a new list from the existing list such that each element in the new list is the product of all the numbers in the existing list except the element in the same position of a new list element.

For example [2,4,5] --> [20,10,8]

I came up with a solution wherein one for-loop, j traverses to the right side of the i-th (current) element while in other for loop, k covers the left side of the elements - Multiplies and gives the result. 

def mulList():
    oldList = [2,4,5]
    newList = []
    for i in range(len(oldList)):
        a = 1
        for j in range(i+1,len(oldList)):
            a *= oldList[j] 
        for j in range(i-1,-1,-1):
            a *= oldList[j] 
        newList.append(a)
    print(newList)
mulList()

Later I got to know that we can solve it with two for-loops like this where I am not doing anything if i equals j

def mulList():
    oldList = [2,4,5]
    newList = []
    for i in range(len(oldList)):
        a = 1
        for j in range(len(oldList)):
            if j == i:
                a += 0
            else:
                a *= oldList[j] 
        newList.append(a)
    print(newList)
mulList()

I was wondering whether there is any better way to solve it with only one for loop.

Upvotes: 1

Views: 87

Answers (4)

Devesh Kumar Singh
Devesh Kumar Singh

Reputation: 20490

You can take the product of all elements in the list via functools.reduce, and then divide each element in the list with the product using integer division //

from functools import reduce
from operator import mul

li = [2,4,5]
#Take product of all elements via reduce operation on the list 
mult = reduce(mul, li)
#40

#Divide the product found in the step above by each item via integer division
res = [mult//item for item in li]

print(res)

You can also multiply elements in a for loop if you don't want to use functools.reduce

#Or loop over the element to multiply
mult = 1
for item in li:
    mult *= item

The output will be

[20, 10, 8]

Upvotes: 2

doca
doca

Reputation: 1548

How about just this

c = 1
for i in oldList:
    c *= i
newList = [c//e for e in oldList]

Now your function will be

def mulList():
    oldList = [2,4,5]
    c = 1
    for i in oldList:
        c *= i
    newList = [c//e for e in oldList]
    print(newList)

Upvotes: 0

Mahi
Mahi

Reputation: 21893

You can just multiply everything together once, and then loop through the elements again and divide the total product with the current element:

def mulList():
    oldList = [2,4,5]
    newList = []
    total = 1
    for x in oldList:
        total *= x  # total = total * x
    for x in oldList:
        # Use // to get int (4) instead of float (4.0)
        newList.append(total // x)
    print(newList)

Upvotes: 4

Albin Paul
Albin Paul

Reputation: 3419

I saw this question in leetcode I think and there was a constraint to not use division and still do this algorithm in O(n). Basically I traverse the array two times once in forward direction and once in reverse and the multipies corresponding elements in the third iteration to get the output you see.

oldlist = [2,4,5]
forwardlist=[1]*len(oldlist)
backwardlist=[1]*len(oldlist)
mul = oldlist[0]
for i in range(1,len(oldlist)):
    forwardlist[i] = mul
    mul*= oldlist[i]
mul = oldlist[len(oldlist) - 1]
for i in range(len(oldlist) - 2, -1, -1):
    backwardlist[i] = mul
    mul*= oldlist[i]
newlist = []
for i in range(len(oldlist)):
    newlist.append(forwardlist[i]*backwardlist[i])
print(newlist)

OUTPUT

[20, 10, 8]

Hope that was helpful. :)

Upvotes: 1

Related Questions