I have an array which it has N number.I would like to multiply array element as the following rule;
arr[n]={5,7,2,3,4....}
the first row:A[0]*A[2]*A[3]*A[4]....*A[n]
the second row:A[0]*A[1]*A[3]*A[4]....*A[n]
the third row:A[0]*A[1]*A[2]*A[4]...*A[n]
...........
the n row:A[0]*A[1]*A[2]*A[3]*A[4]....*A[n-1]
i did it with O(n^2) but i couldn't solve it O(n) how can i do that without division row element ?
Assuming no zeros in the array, a possible approach could be
product = A[0]*...*A[n]
first = product / A[1]
second = product / A[2]
....
If division is not allowed, you can utilize left and right running products and do something like this:
int P[N], Q[N];
P[0] = A[0];
for(int i = 1; i < N; ++i)
P[i] = P[i - 1] * A[i];
Q[N-1] = A[N-1];
for(int i = N-2; i >= 0; --i)
Q[i] = Q[i+1] * A[i];
for(int i = 1; ....)
R[i] = P[i-1] * Q[i+1];
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加