Multiplication of numbers.

There is an array A[N] of N numbers. You have to compose 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].

Example:
A: {4, 3, 2, 1, 2}
OUTPUT: {12, 16, 24, 48, 24}.

C++:
01 int* genMatrix(int* A, int size)
02 {
03     int* B=new int[size];
04     int* C=new int[size];
05     int* D=new int[size];
06     int tmp=1;
07     for(int i=0;i<size;i++){
08         tmp*=A[i];
09         B[i]=tmp;
10     }
11     tmp=1;
12     for(int i=size1;i>=0;i){
13         tmp*=A[i];
14         C[i]=tmp;
15     }
16     D[0]=C[1];
17     D[size1]=B[size2];
18     for(int i=1;i<size1;i++){
19         D[i]=B[i1]*C[i+1];
20     }
21     return D;
22 }
Advertisements
This entry was posted in Array and linked list, Dynamic programming. Bookmark the permalink.

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