A Product Array Puzzle | Set 3

0 0 8 minutes read

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 i^th position will be equal M/arr[i].
The divisions of two numbers can be performed by using the property of logarithm and exp functions.
- $log(a) - log(b) = log(a/b)$
- $exp(log(a/b)) = a/b$
- $exp(log(a) - log(b)) = a/b$
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) space
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])
            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 Code
int 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) space
static 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 Code
public 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 approach
import math
 
# Function to form product array
# with O(n) time and O(1) space
def 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 Code
arr = [ 10, 3, 5, 6, 2 ]
N = len(arr) 
 
# Function Call
productExceptSelf(arr, N)
 
# This code is contributed by code_hunt.

C#

// C# program for the above approach
using System;
class GFG
{
     
// Function to form product array
// with O(n) time and O(1) space
static 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 Code
public 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) space
function 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 zambiatek!