Greedy_exceptIndexMutliplier

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#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=[1]*len(arr)
	currentproduct=1
	i=0
	while(i<len(arr)):
		productbeforeeachindex[i]*=currentproduct
		currentproduct*=arr[i]
		i+=1
	#find products after each index by starting at end and going back towards the start and put it in an array
	productaftereachindex=[1]*len(arr)
	currentproduct=1
	j=len(arr)-1
	while(j>=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=[1]*len(arr)
	currentproduct=1
	i=0
	while(i<len(arr)):
		productbeforeeachindex[i]=currentproduct
		currentproduct*=arr[i]
		i+=1
	#find products after each index by starting at end and going back towards the start and put it in an array
	productexceptatindex=[1]*len(arr)
	currentproduct=1
	j=len(arr)-1
	while(j>=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]))