In this tutorial, I am going to discuss a very interesting problem Product of array except self or product of every integer except the integer at that index.
Given an array of N integers where N > 1. Write a code to print the result/output such that result[i] is equal to the product of all the elements of an array except self (result[i]).
For example –
Input: {4, 2, 1, 7}
Output: {14, 28, 56, 8}
NOTE: We have to solve this problem without division and in linear time O(n).
As per the problem statement, division operation is not allowed. Solving this problem using division operation is just a cakewalk. But the problem constraint is that we cannot use the division constraint. Before seeing the solution, Think for a moment about how you can solve this problem if division operation is not allowed.
I have shared the link of the video tutorial at the end of this post.
Product of Array Except Self with Division – Java Code
Suppose, if division constraint is not given then how we can solve this problem. In the next approach, we can solve this problem without using division operation.
i) First calculate the product of all the numbers of an array.
ii) Divide the product we obtain with the number present at each index.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
/* Product of every integer except the integer at that index using division operation */ public class ProductExceptSelf { public static int[] findProductUsingDivision(int[] nums) { int len = nums.length; int[] ans = new int[len]; int prod = 1; //Find product of all the integers of an array for(int i = 0; i < nums.length; i++) { prod = prod * nums[i]; } for(int i = 0; i < nums.length; i++) { ans[i] = prod/nums[i]; } return ans; } public static void main(String[] args) { int[] arr = {4, 2, 1, 7}; int[] result = findProductUsingDivision(arr); for(int i = 0; i < result.length; i++) { System.out.print(result[i] + " "); } } } |
We have discussed the approach to find product of array except self if division is allowed. Let’s solve this problem without using division operation.
Find maximum sum of a subarray of size k
Product of Array Except Self – Java Code
To calculate the product at given i index. We need to find the product of all the numbers present to the left of i and product of all the numbers to the right of i. After that do the product of left and right numbers to get the answer.
I have also explained this approach using a video tutorial. The link is present at the end of this post.
Here are the following steps to implement this logic.
i) Declare two empty arrays left and right. The left[i] would contain the product of all the numbers to the left of i. The right[i] would contain the product of all the numbers to the right of i.
ii) Two fill these two arrays we need two for loops. For the left array, the value at left[0] would be 1. For rest of the elements we simply use this expression left[i] = left[i-1] * nums[i-1] where nums is the input array.
Now take right array and let’s do the same steps in a reverse order. The value at right[n-1] would be 1. For rest of the elements we use this expression right[i] = right[i+1] * nums[i+1].
iii) Once we filled the right and left array. Then the product at given index is the product of left[i] * right[i].
The time complexity of this approach is O(n). The space complexity is also O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
/* Find the product of all the numbers of an array at given index without including that number. */ public class ProductExceptSelf { public static int[] findProductExceptSelf(int[] nums) { //Array Length int len = nums.length; //Declare three arrays int[] left = new int[len]; int[] right = new int[len]; int[] ans = new int[len]; left[0] = 1; for(int i = 1; i < nums.length; i++) { left[i] = left[i-1] * nums[i-1]; } right[len - 1] = 1; for(int i = len-2; i >= 0; i--) { right[i] = right[i+1] * nums[i+1]; } for(int i = 0; i < len; i++) { ans[i] = left[i] * right[i]; } return ans; } public static void main(String[] args) { int[] arr = {4, 2, 1, 7}; int[] result = findProductExceptSelf(arr); for(int i = 0; i < result.length; i++) { System.out.print(result[i] + " "); } } } |
We can solve this problem in constant space by getting rid of the left and right arrays. In this example, let’s solve this problem without using extra space.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/* Product of all elements in array except self. */ public class ProductExceptSelf { public static int[] findProduct(int[] nums) { int len = nums.length; int[] ans = new int[len]; //Find left product ans[0] = 1; for(int i = 1; i < nums.length; i++) { ans[i] = ans[i-1] * nums[i-1]; } int right = 1; for(int i = len-1; i >= 0; i--) { ans[i] = ans[i] * right; right = right * nums[i]; } return ans; } public static void main(String[] args) { int[] arr = {4, 2, 1, 7}; int[] result = findProductExceptSelf(arr); for(int i = 0; i < result.length; i++) { System.out.print(result[i] + " "); } } } |
