Given an array arr[] consisting of N integers, the task is to construct a Product array of the same size without using division (‘/’) operator such that each array element becomes equal to the product of all the elements of arr[] except arr[i].
Examples:
Input: arr[] = {10, 3, 5, 6, 2}
Output: 180 600 360 300 900
Explanation:
3 * 5 * 6 * 2 is the product of all array elements except 10 is 180
10 * 5 * 6 * 2 is the product of all array elements except 3 is 600.
10 * 3 * 6 * 2 is the product of all array elements except 5 is 360.
10 * 3 * 5 * 2 is the product of all array elements except 6 is 300.
10 * 3 * 6 * 5 is the product of all array elements except 2 is 9.Input: arr[] = {1, 2, 1, 3, 4}
Output: 24 12 24 8 6
Approach: The idea is to use log() and exp() functions instead of log10() and pow(). Below are some observations regarding the same:
- Suppose M is the multiplication of all the array elements then the element of output array at ith position will be equal M/arr[i].
- The divisions of two numbers can be performed by using the property of logarithm and exp functions.
- The logarithmic function is not defined for numbers less than zero so to maintain the such cases separately.
Follow the steps below to solve the problem:
- Initialize two variables, say product = 1 and Z = 1, to store the product of array and count of zero elements.
- Traverse the array and multiply the product by arr[i] if arr[i] is not equal to 0. Otherwise, increment count of Z by one.
- Traverse the array arr[] and perform the following:
- If Z is 1 and arr[i] is not zero then update arr[i] as arr[i] = 0 and continue.
- Otherwise, if Z is 1 and arr[i] is 0 then update arr[i] as product and continue.
- Otherwise, if Z is greater than 1 then assign arr[i] as 0 and continue.
- Now find the value of abs(product)/abs(arr[i]) using the formula discussed above and store it in a variable say curr.
- If the value of arr[i] and product is negative or if arr[i] and product is positive then assign arr[i] as curr.
- Otherwise, assign arr[i] as -1*curr.
- After completing the above steps, print the array arr[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to form product array// with O(n) time and O(1) spacevoid productExceptSelf(int arr[], int N){ // Stores the product of array int product = 1; // Stores the count of zeros int z = 0; // Traverse the array for (int i = 0; i < N; i++) { // If arr[i] is not zero if (arr[i]) product *= arr[i]; // If arr[i] is zero then // increment count of z by 1 z += (arr[i] == 0); } // Stores the absolute value // of the product int a = abs(product), b; for (int i = 0; i < N; i++) { // If Z is equal to 1 if (z == 1) { // If arr[i] is not zero if (arr[i]) arr[i] = 0; // Else else arr[i] = product; continue; } // If count of 0s at least 2 else if (z > 1) { // Assign arr[i] = 0 arr[i] = 0; continue; } // Store absolute value of arr[i] int b = abs(arr[i]); // Find the value of a/b int curr = round(exp(log(a) - log(b))); // If arr[i] and product both // are less than zero if (arr[i] < 0 && product < 0) arr[i] = curr; // If arr[i] and product both // are greater than zero else if (arr[i] > 0 && product > 0) arr[i] = curr; // Else else arr[i] = -1 * curr; } // Traverse the array arr[] for (int i = 0; i < N; i++) { cout << arr[i] << " "; }}// Driver Codeint main(){ int arr[] = { 10, 3, 5, 6, 2 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call productExceptSelf(arr, N); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{// Function to form product array// with O(n) time and O(1) spacestatic void productExceptSelf(int arr[], int N){ // Stores the product of array int product = 1; // Stores the count of zeros int z = 0; // Traverse the array for (int i = 0; i < N; i++) { // If arr[i] is not zero if (arr[i] != 0) product *= arr[i]; // If arr[i] is zero then // increment count of z by 1 if (arr[i] == 0) z += 1; } // Stores the absolute value // of the product int a = Math.abs(product); for (int i = 0; i < N; i++) { // If Z is equal to 1 if (z == 1) { // If arr[i] is not zero if (arr[i] != 0) arr[i] = 0; // Else else arr[i] = product; continue; } // If count of 0s at least 2 else if (z > 1) { // Assign arr[i] = 0 arr[i] = 0; continue; } // Store absolute value of arr[i] int b = Math.abs(arr[i]); // Find the value of a/b int curr = (int)Math.round(Math.exp(Math.log(a) - Math.log(b))); // If arr[i] and product both // are less than zero if (arr[i] < 0 && product < 0) arr[i] = curr; // If arr[i] and product both // are greater than zero else if (arr[i] > 0 && product > 0) arr[i] = curr; // Else else arr[i] = -1 * curr; } // Traverse the array arr[] for (int i = 0; i < N; i++) { System.out.print(arr[i] + " "); }}// Driver Codepublic static void main(String args[]){ int arr[] = { 10, 3, 5, 6, 2 }; int N = arr.length; // Function Call productExceptSelf(arr, N);}}// This code is contributed by splevel62. |
Python3
# Python 3 program for the above approachimport math# Function to form product array# with O(n) time and O(1) spacedef productExceptSelf(arr, N) : # Stores the product of array product = 1 # Stores the count of zeros z = 0 # Traverse the array for i in range(N): # If arr[i] is not zero if (arr[i] != 0) : product *= arr[i] # If arr[i] is zero then # increment count of z by 1 if(arr[i] == 0): z += 1 # Stores the absolute value # of the product a = abs(product) for i in range(N): # If Z is equal to 1 if (z == 1) : # If arr[i] is not zero if (arr[i] != 0) : arr[i] = 0 # Else else : arr[i] = product continue # If count of 0s at least 2 elif (z > 1) : # Assign arr[i] = 0 arr[i] = 0 continue # Store absolute value of arr[i] b = abs(arr[i]) # Find the value of a/b curr = round(math.exp(math.log(a) - math.log(b))) # If arr[i] and product both # are less than zero if (arr[i] < 0 and product < 0): arr[i] = curr # If arr[i] and product both # are greater than zero elif (arr[i] > 0 and product > 0): arr[i] = curr # Else else: arr[i] = -1 * curr # Traverse the array arr[] for i in range(N): print(arr[i], end = " ") # Driver Codearr = [ 10, 3, 5, 6, 2 ]N = len(arr) # Function CallproductExceptSelf(arr, N)# This code is contributed by code_hunt. |
C#
// C# program for the above approachusing System;class GFG{ // Function to form product array// with O(n) time and O(1) spacestatic void productExceptSelf(int[] arr, int N){ // Stores the product of array int product = 1; // Stores the count of zeros int z = 0; // Traverse the array for (int i = 0; i < N; i++) { // If arr[i] is not zero if (arr[i] != 0) product *= arr[i]; // If arr[i] is zero then // increment count of z by 1 if (arr[i] == 0) z += 1; } // Stores the absolute value // of the product int a = Math.Abs(product); for (int i = 0; i < N; i++) { // If Z is equal to 1 if (z == 1) { // If arr[i] is not zero if (arr[i] != 0) arr[i] = 0; // Else else arr[i] = product; continue; } // If count of 0s at least 2 else if (z > 1) { // Assign arr[i] = 0 arr[i] = 0; continue; } // Store absolute value of arr[i] int b = Math.Abs(arr[i]); // Find the value of a/b int curr = (int)Math.Round(Math.Exp(Math.Log(a) - Math.Log(b))); // If arr[i] and product both // are less than zero if (arr[i] < 0 && product < 0) arr[i] = curr; // If arr[i] and product both // are greater than zero else if (arr[i] > 0 && product > 0) arr[i] = curr; // Else else arr[i] = -1 * curr; } // Traverse the array arr[] for (int i = 0; i < N; i++) { Console.Write(arr[i] + " "); }}// Driver Codepublic static void Main(String[] args){ int[] arr = { 10, 3, 5, 6, 2 }; int N = arr.Length; // Function Call productExceptSelf(arr, N);}}// This code is contributed by sanjoy_62. |
Javascript
<script>// Javascript Program to check matrix// is scalar matrix or not. // Function to form product array// with O(n) time and O(1) spacefunction productExceptSelf(arr, N){ // Stores the product of array let product = 1; // Stores the count of zeros let z = 0; // Traverse the array for (let i = 0; i < N; i++) { // If arr[i] is not zero if (arr[i] != 0) product *= arr[i]; // If arr[i] is zero then // increment count of z by 1 if (arr[i] == 0) z += 1; } // Stores the absolute value // of the product let a = Math.abs(product); for (let i = 0; i < N; i++) { // If Z is equal to 1 if (z == 1) { // If arr[i] is not zero if (arr[i] != 0) arr[i] = 0; // Else else arr[i] = product; continue; } // If count of 0s at least 2 else if (z > 1) { // Assign arr[i] = 0 arr[i] = 0; continue; } // Store absolute value of arr[i] let b = Math.abs(arr[i]); // Find the value of a/b let curr = Math.round(Math.exp(Math.log(a) - Math.log(b))); // If arr[i] and product both // are less than zero if (arr[i] < 0 && product < 0) arr[i] = curr; // If arr[i] and product both // are greater than zero else if (arr[i] > 0 && product > 0) arr[i] = curr; // Else else arr[i] = -1 * curr; } // Traverse the array arr[] for (let i = 0; i < N; i++) { document.write(arr[i] + " "); }} // Driver Code let arr = [ 10, 3, 5, 6, 2 ]; let N = arr.length; // Function Call productExceptSelf(arr, N);// This code is contributed by souravghosh0416.</script> |
Output:
180 600 360 300 900
Time Complexity: O(N)
Auxiliary Space: O(1)
Alternate Approaches: Please refer to the previous posts of this article for alternate approaches:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
