Finding the Product of Array Except Itself which requires finding the product of all elements in an array, except for the element at a given index. Without the division operator, this problem can be solved efficiently in O(n) time. <\/p>\n\n\n\n
Here is the problem statement: “We are given an array of numbers, and for each element in the array, we need to find the product of all the other elements except itself.<\/strong>“<\/p>\n\n\n\n Let us understand it better with an example:<\/p>\n\n\n\n Numbers = [2,3,5,4,1]<\/p>\n\n\n For the 0th index, the result will be the product of elements from index 1 to 4, i.e. 3*5*4*1 = 60. Similarly, it is calculated for the rest of the indexes.<\/p>\n\n\n In this approach, we will use a prefix and suffix array in a prefix array. We will maintain the product of the element of the array till that element from the start of the array for every element. In a suffix array, we will maintain the product of the element of the array till that element from the last of the array.<\/p>\n\n\n Here is the C++ program to find the product of array except itself:<\/p>\n\n\n\n Below is the Java program to solve it:<\/p>\n\n\n\n Here is the implementation in Python as well:<\/p>\n\n\n\n Output:<\/strong><\/p>\n\n\n\n The time complexity of this approach is O(n) as Calculating the prefix array takes O(n) time, where n is the size of the input array, Calculating the suffix array also takes O(n) time, calculating the product of prefix[i] * sufix[i] array takes O(n) time. So The overall time complexity is O(n).<\/p>\n\n\n\n The space complexity of this approach is O(n)+O(n) as we are using prefix array and suffix array of size n where n is the size of the given array.<\/p>\n\n\n\n Now, you can solve another problem called Subarray Sum Equals K<\/a>, which is also asked a lot in interviews.<\/p>\n\n\n\n![\"Example](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-10-1024x201.png\")
<\/figure>\n<\/div>\n\n\n
Output = [60,40,24,30,120]<\/p>\n\n\n\n![\"Explanation](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-14-1024x311.png\")
<\/figure>\n<\/div>\n\n\nUsing Prefix and Suffix Arrays to Solve this Problem<\/strong><\/h3>\n\n\n\n
![\"Prefix](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-4-1024x218.png\")
<\/figure>\n<\/div>\n\n\n\n
![\"calculate](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/4-7-1024x290.png\")
<\/figure>\n<\/div>\n\n\n\n
![\"calculate](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/5-3-1024x233.png\")
<\/figure>\n<\/div>\n\n\n\n
![\"find](\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/6-2-1024x347.png\")
<\/figure>\n<\/div>\n\n\nC++ Code<\/strong><\/h3>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\n\nvector<int> productExceptSelf(vector<int>& nums) {\n int n = nums.size();\n \n \/\/ Initialize arrays to store prefix and suffix products\n vector<int> prefix(n, 1); \/\/ Prefix product of elements to the left\n vector<int> suffix(n, 1); \/\/ Suffix product of elements to the right\n vector<int> prod(n); \/\/ Final product array\n\n \/\/ Calculate prefix products\n for (int i = 1; i < n; i++) {\n prefix[i] = prefix[i - 1] * nums[i - 1];\n }\n\n \/\/ Calculate suffix products\n for (int i = n - 2; i >= 0; i--) {\n suffix[i] = suffix[i + 1] * nums[i + 1];\n }\n\n \/\/ Calculate the final product array\n for (int i = 0; i < n; i++) {\n prod[i] = prefix[i] * suffix[i];\n }\n\n return prod;\n}\n\nint main() {\n vector<int> nums = {2, 3, 5, 4, 1};\n vector<int> prod = productExceptSelf(nums);\n\n cout << "The product array is: ";\n for (int num : prod) {\n cout << num << " ";\n }\n cout << endl;\n\n return 0;\n}<\/pre><\/div>\n\n\n\nJava Code<\/strong><\/h3>\n\n\n\n
import java.util.Arrays;\n\npublic class ProductExceptSelf {\n public static int[] productExceptSelf(int[] nums) {\n int n = nums.length;\n\n \/\/ Initialize arrays to store prefix and suffix products\n int[] prefix = new int[n]; \/\/ Prefix product of elements to the left\n int[] suffix = new int[n]; \/\/ Suffix product of elements to the right\n int[] prod = new int[n]; \/\/ Final product array\n\n \/\/ Calculate prefix products\n prefix[0] = 1;\n for (int i = 1; i < n; i++) {\n prefix[i] = prefix[i - 1] * nums[i - 1];\n }\n\n \/\/ Calculate suffix products\n suffix[n - 1] = 1;\n for (int i = n - 2; i >= 0; i--) {\n suffix[i] = suffix[i + 1] * nums[i + 1];\n }\n\n \/\/ Calculate the final product array\n for (int i = 0; i < n; i++) {\n prod[i] = prefix[i] * suffix[i];\n }\n\n return prod;\n }\n\n public static void main(String[] args) {\n int[] nums = {2, 3, 5, 4, 1};\n int[] prod = productExceptSelf(nums);\n\n System.out.print("The product array is: ");\n System.out.println(Arrays.toString(prod));\n }\n}<\/pre><\/div>\n\n\n\nPython Code<\/strong><\/h3>\n\n\n\n
def product_except_self(nums):\n n = len(nums)\n \n # Initialize arrays to store prefix and suffix products\n prefix = [1] * n # Prefix product of elements to the left\n suffix = [1] * n # Suffix product of elements to the right\n prod = [0] * n # Final product array\n\n # Calculate prefix products\n for i in range(1, n):\n prefix[i] = prefix[i - 1] * nums[i - 1]\n\n # Calculate suffix products\n for i in range(n - 2, -1, -1):\n suffix[i] = suffix[i + 1] * nums[i + 1]\n\n # Calculate the final product array\n for i in range(n):\n prod[i] = prefix[i] * suffix[i]\n\n return prod\n\nnums = [2, 3, 5, 4, 1]\nprod = product_except_self(nums)\n\nprint("The product array is:", prod)<\/pre><\/div>\n\n\n\nThe product array is: [60, 40, 24, 30, 120]<\/code><\/pre>\n\n\n\nConclusion<\/strong><\/h2>\n\n\n\n