Product of array except self
Written by
Product of array except self problem
Input: [1,2,3,4]
Output: [24,12,8,6]
Array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Note: Please solve it without division and in O(n).
# Brute Force
- Construct a temporary array left[] such that left[i] contains product of all elements on left of arr[i] excluding arr[i].
- Construct another temporary array right[] such that right[i] contains product of all elements on on right of arr[i] excluding arr[i].
- To get product array, multiply left[] and right[].
Code :
#include <bits/stdc++.h> using namespace std;
void productArray(int arr[], int n) { if (n == 1) { cout << 0; return; } int *left = new int[sizeof(int) *n]; int *right = new int[sizeof(int) *n]; int *prod = new int[sizeof(int) *n];
int i, j; left[0] = 1; right[n - 1] = 1; for (i = 1; i < n; i++) left[i] = arr[i - 1] *left[i - 1]; for (j = n - 2; j >= 0; j--) right[j] = arr[j + 1] *right[j + 1]; for (i = 0; i < n; i++) prod[i] = left[i] *right[i]; for (i = 0; i < n; i++) cout << prod[i] << " "; return;
}
int main() { int arr[] = { 10, 3, 5, 6, 2 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "The product array is: \n"; productArray(arr, n); }
Time Complexity: O(n)
Space Complexity: O(n)
# Optimized Solution
The approach here will be to minimize the space required by the left and the right array.
Code :
#include <bits/stdc++.h> using namespace std; void productArray(int arr[], int n) { if (n == 1) { cout << 0; return; }
int i, temp = 1; int *prod = new int[(sizeof(int) *n)]; memset(prod, 1, n); for (i = 0; i < n; i++) { prod[i] = temp; temp *= arr[i]; } temp = 1; for (i = n - 1; i >= 0; i--) { prod[i] *= temp; temp *= arr[i]; } for (i = 0; i < n; i++) cout << prod[i] << " "; return;
}
int main() { int arr[] = { 10, 3, 5, 6, 2 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "The product array is: \n"; productArray(arr, n); }
Time Complexity: O(n)
Space Complexity: O(n)
The output will be the same for both approaches:
180,600,360,300,900