Problem
Given an integer array arr, there are n integers (n > 1), return an array output such that output[i] is equal to the product of all the elements in the original array except arr[i].
Example:
Given: [1,2,3,4]
result: [24,12,8,6]
Follow up: Please solve it without division and in O(n).
Follow up:
Please solve it with extra space complexity O(1)?
Solution
We should clear that we can make assumption that the products of all the elements are still within the 32 bit integer range.
If we have the total product, then divide the value in the current position, then we get the answer. However, if we can not use divide, we have to multiply the elements except the value at the current position in order to get the same answer.
If we have the total product, then divide the value in the current position, then we get the answer. However, if we can not use divide, we have to multiply the elements except the value at the current position in order to get the same answer.
How to multiply the elements except the value at the current position? We can first multiply the elements on the left, then multiply the elements on the right. We can use two arrays to save the product of elements on the left and the product of elements on the right. Loop the array twice can fill up the 2 arrays, then we multiply the two arrays for the answer. Actually, we can save one of arrays, use a variable in stead.
public class ProductArray {
public static int[] product(int[] a) {
//1,2,3,4
int N = a.length;//4
int[] result = new int[N];
result[0] = 1;
for(int i = 1; i < N; i++) {//1,1,2,6
result[i] = result[i-1] * a[i-1];
}
int right = 1;//24,12,8,6
for(int i = N - 2; i >=0; i--) { //1
right = right * a[i+1];//24
result[i] = result[i] * right; //6*1
}
return result;
}
public static void main(String...args) {
for(int i : product(new int[]{1,2,3,4})) {
System.out.print(i + " ");
}
}
}
public static int[] product(int[] a) {
//1,2,3,4
int N = a.length;//4
int[] result = new int[N];
result[0] = 1;
for(int i = 1; i < N; i++) {//1,1,2,6
result[i] = result[i-1] * a[i-1];
}
int right = 1;//24,12,8,6
for(int i = N - 2; i >=0; i--) { //1
right = right * a[i+1];//24
result[i] = result[i] * right; //6*1
}
return result;
}
public static void main(String...args) {
for(int i : product(new int[]{1,2,3,4})) {
System.out.print(i + " ");
}
}
}
Time cost O(N), space cost O(1).
