Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# charles2588/Greedy_exceptIndexMutliplier.py

Created Jul 1, 2016
https://repl.it/C8Cl/1 created by charles2588
 #Find product of all other numbers in the array for a given index except the number at that index.for ex. [1,2,3] = [6(3*2),3(1*3),2(1*2)] def multiplier(arr): result=[1 for i in arr] #Brute force for i in range(len(arr)): for j in range(len(arr)): if j==i: continue else: result[i]=result[i]*arr[j] return result def multiplier2(arr): #Greedy to avoid multipying same numbers again. #find products before each index and progressing towards the end and put it in an array productbeforeeachindex=*len(arr) currentproduct=1 i=0 while(i=0): productaftereachindex[j]*=currentproduct currentproduct*=arr[j] j-=1 #at each index...multipy (product before and after that index) productexceptatindex=[None]*len(arr) for i in range(len(productexceptatindex)): productexceptatindex[i]=productbeforeeachindex[i]*productaftereachindex[i] return productexceptatindex def multiplier3(arr): #find products before each index and progressing towards the end and put it in an array productbeforeeachindex=*len(arr) currentproduct=1 i=0 while(i=0): productexceptatindex[j]=productbeforeeachindex[j]*currentproduct currentproduct*=arr[j] j-=1 return productexceptatindex print(multiplier([2, 7, 3, 4])) print(multiplier([3, 0, 3, 4])) print(multiplier2([2, 7, 3, 4])) print(multiplier3([2, 7, 3, 4]))
 Python 3.5.1 (default, Dec 2015, 13:05:11) [GCC 4.8.2] on linux >>> [84, 24, 56, 42] [0, 36, 0, 0] [84, 24, 56, 42] [84, 24, 56, 42] => None
to join this conversation on GitHub. Already have an account? Sign in to comment