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}
A:
Tiger's own solution is to use another two array to store the left and right muliplication result.
,
private static int[] multi(int[] A) {
// use another matrix to help record its left multiplication result, and right
int n = A.length;
if(n==0){
System.err.print("array should have at least 1");
System.exit(0);
}
int[] left = new int[n];
int[] right = new int[n];
left[0] =1;
for(int i =1;i<n;i++) // calculate the left part
left[i]=left[i-1] * A[i-1];
right[n-1] = 1;
for(int i = n-2;i>=0;i--)
right[i] = right[i+1] * A[i+1];
int[] output = new int[n];
for(int i =0;i<n;i++)
output[i] = left[i] * right[i];
return output;
}
But above would require O(n) space
To save space ,we can use the right matrix to replace the output matrix,
as follows
private static int[] multi(int[] A) {
// use another matrix to help record its left multiplication result, and right
int n = A.length;
if(n==0){
System.err.print("array should have at least 1");
System.exit(0);
}
int[] left = new int[n];
int[] right = new int[n];
left[0] =1;
for(int i =1;i<n;i++) // calculate the left part
left[i]=left[i-1] * A[i-1];
right[n-1] = 1;
for(int i = n-2;i>=0;i--)
right[i] = right[i+1] * A[i+1];
for(int i =0;i<n;i++)
right[i] = left[i] * right[i];
return right;
}
Further, let's try to eliminate the left array.
After analyzing, we saw that the left value could be calculated iteratively in the loop. thus, we got following.
private static int[] multi(int[] A) {
// use another matrix to help record its left multiplication result, and right
int n = A.length;
if(n==0){
System.err.print("array should have at least 1");
System.exit(0);
}
int leftTillNow = 1;
// record the multiplication result of its right sided, from i+1 to n-1
int [] output = new int[n];
output[n-1] = 1;
for(int i = n-2;i>=0;i--)
output[i] = output[i+1] * A[i+1];
for(int i =1;i<n;i++){
output[i] = leftTillNow * output[i];
leftTillNow *= A[i-1];
}
return output;
}
No comments:
Post a Comment