Array of A[N] of N numbers. Create Output[N] : Output[i] = multiplication of all the elements of A[N] except A[i]. Solve it without division operator in O(n)

Here is the simple Algorithm explanation and code in ( python ) for the problem given here

Problem

Try solving this in O(n)..

You are given a list of A[N] of N numbers. Create an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. Solve it without division operator and in O(n). For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

http://www.linkedin.com/groups/Try-solving-this-in-O-1920463.S.165328313?qid=cf1bdabc-e4e1-489e-8557-e3ba125bb4cd&trk=group_most_popular-0-b-ttl&goback=%2Egmp_1920463

My Approach to this problem

Do 2 iterations of the array – starting once from the beginning of the array and once from the end and during each iteration calculate the running multiplication and store the results in 2 different arrays – pre[] and post[]

The results as asked in the algorithm is multiplication is the current index location pre[j-1] * post[j+1] – A special handling of the 2 edge cases when the index is at the end of the array is needed

For Example

if the input array is

pre = [7, 7, 14, 42, 168, 840, 5040]
post = [5040, 720, 720, 360, 120, 30, 6]

Python Code

l = [7,1,2,3,4,5,6]
pre=[]
po=[]

# Create an array which is a running multiple from start of the array
for j in range(0, len(l)):
if j == 0:
multiple = l[j]
else:
multiple = multiple * l[j]
pre.append(multiple)
print pre

# Create an array which is a running multiple from end of the array
for j in range(len(l)-1, -1, -1):
if (j == len(l) – 1):
multiple = l[j]
else:
multiple = multiple*l[j]
po.append(multiple)
po.reverse()

print po

# result of each multiplication is the current index location pre[j-1] * po[j+1]
# special handling of the 2 edge cases
for j in range(0, len(l)):
if j == 0:
print po[j+1]
elif (j == (len(l) – 1)):
print pre[j-1]
else:
print pre[j-1]*po[j+1]

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s