"Bidirectionally multiplied" array
Another small problem before I go to sleep tonight:
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]. 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]. Solve it without division operator and in O(n).
What is funny of the problem, is the fact that the O(n) constraint, makes it sound like is going to be hard to solve. Doesn’t it? Well, it’s not.
The solution is quite simple, so I suggest you take your 10 minutes to think about it, then continue to see the code.
int *bidirectionally_multiplied_array(const int *A, int size_A) {
int *multi_left_to_right, *multi_right_to_left, *output;
int i;
// Make some space for calculation...
multi_left_to_right = malloc(size_A * sizeof(int));
multi_right_to_left = malloc(size_A * sizeof(int));
output = malloc(size_A * sizeof(int));
// Multiply the elements "from left to right"...
multi_left_to_right[0] = A[0];
for ( i = 1; i < size_A; ++i ) {
multi_left_to_right[i] = multi_left_to_right[i-1] * A[i];
}
// Multiply the elements "from right to left"...
multi_right_to_left[size_A-1] = A[size_A-1];
for ( i = size_A-2; i >= 0; --i ) {
multi_right_to_left[i] = multi_right_to_left[i+1] * A[i];
}
// First and Last element are "special case"
output[0] = multi_right_to_left[1];
output[size_A-1] = multi_left_to_right[size_A-2];
for ( i = 1; i < size_A-1; ++i ) {
output[i] = multi_left_to_right[i-1] * multi_right_to_left[i+1];
}
free(multi_left_to_right);
free(multi_right_to_left);
return output;
}