Multiplication of numbers | LeetCode
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).
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}
Let’s define array B where element B[i] = multiplication of numbers from A[0] to A[i]. For example, if A = {4, 3, 2, 1, 2}, then B = {4, 12, 24, 24, 48}. Then, we scan the array A from right to left, and have a temporary variable called product which stores the multiplication from right to left so far. Calculating OUTPUT[i] is straight forward, as OUTPUT[i] = B[i-1] * product.
The above method requires only O(n) time but uses O(n) space. We have to trade memory for speed. Is there a better way? (i.e., runs in O(n) time but without extra space?)
Yes, actually the temporary table is not required. We can have two variables called left and right, each keeping track of the product of numbers multiplied from left->right and right->left
Example:
A: {4, 3, 2, 1, 2}
OUTPUT: {12, 16, 24, 48, 24}
Let’s define array B where element B[i] = multiplication of numbers from A[0] to A[i]. For example, if A = {4, 3, 2, 1, 2}, then B = {4, 12, 24, 24, 48}. Then, we scan the array A from right to left, and have a temporary variable called product which stores the multiplication from right to left so far. Calculating OUTPUT[i] is straight forward, as OUTPUT[i] = B[i-1] * product.
The above method requires only O(n) time but uses O(n) space. We have to trade memory for speed. Is there a better way? (i.e., runs in O(n) time but without extra space?)
Yes, actually the temporary table is not required. We can have two variables called left and right, each keeping track of the product of numbers multiplied from left->right and right->left
void array_multiplication(int A[], int OUTPUT[], int n) {
int left = 1;
int right = 1;
for (int i = 0; i < n; i++)
OUTPUT[i] = 1;
for (int i = 0; i < n; i++) {
OUTPUT[i] *= left;
OUTPUT[n - 1 - i] *= right;
left *= A[i];
right *= A[n - 1 - i];
}
}
Read full article from Multiplication of numbers | LeetCode