C++ Program For Product Array Puzzle

In this post, we will explore various approaches to solving product array puzzles using C++.

Problem statement:

We have been provided with an array of integers, and our task is to generate a new array of equal size to the original array, where each element in the new array is the result of multiplying all elements in the original array except for the element at index i.

Input format:

We are taking an integer array:

Example nums = {1, 2, 3, 4, 5}

Output format:

We need to display the array elements after performing the aforementioned operations.

Example: the resulting array is denoted as product = {120, 60, 40, 30, 24}

Explanation:

Product[0] = 234*5

Product[1] = 134*5

Product[2] = 124*5

Product[3] = 123*5

Product[4] = 123*4

There are numerous methods to address the provided issue. In this discussion, we explore 4 strategies to tackle the problem at hand, all of which involve circumventing the usage of the division operator.

Method 1: Bruth Force Method

Let's consider an illustration to showcase the product array puzzle by employing the Brute Force Method in C++.

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int n=5;
    int nums[5] = {1,2,3,4,5};
    for(int i=0; i<n; i++){
        int left = i-1;
        int right = i+1;
        int mul = 1;
        while(left>= 0){
            mul = mul*nums[left];
            left--;
        }
        while(right<n){
            mul = mul*nums[right];
            right++;
        }
        cout << mul <<" ";
    }
    return 0;
}

Output:

Explanation:

There is a variable n representing the array's length, accompanied by an array consisting of integers. Within the provided code, a pair of loops are in operation. The initial loop is responsible for iterating through the array. Subsequently, the inner loop involves three distinct variables: left, right, and mul. The left variable undergoes a decrement operation to calculate the product of numbers preceding the current index, while the right variable experiences an increment operation to determine the product of numbers succeeding the current index. These two variables, left and right, are managed within individual while loops. Upon computing the products of elements situated to the left and right of the index, the resultant multiplication is displayed.

Method 2: Using the pow method

Let's consider an instance to showcase the product array challenge using the pow function in C++:

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int n = 5;
    int nums[5] = {1,2,3,4,5};
    int mul = 1;
    for(int i=0; i<n; i++){
        mul = mul*nums[i];
    }
    cout << "Total product is "<< mul << endl;
    for(int i=0; i<n; i++){
        cout << mul * pow(nums[i],-1) << " ";
    }
}

Output:

Explanation:

This code includes a single for loop that goes through the provided array to calculate the overall product of the array elements, storing it in the variable named mul. Following this, another for loop is utilized to iterate through the array once more. In this iteration, the product of all elements is multiplied by the power of the current element minus one. This essentially involves multiplying the reciprocal of the current element by the total product, resulting in the anticipated outcome.

Method 3: Using a left product and a right product

Let's consider an example to showcase the product array problem by utilizing the left and right product techniques in C++.

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int n = 5;
    int nums[n] = {10, 3, 5, 6, 2};
    int left[n];
    int right[n];
    for(int i=0; i<n; i++){
        left[i] =1;
        right[i] =1;
    }
    // Filling left array
    left[0] = nums[0];
    for(int i=1; i<n; i++){
        left[i] = left[i-1]*nums[i];
    }
    // Filling right array
    right[n-1] = nums[n-1];
    for(int i=n-2; i>=0; i--){
        right[i] = right[i+1]*nums[i];
    }
    cout << right[1] << " ";
    for(int i=1; i<n-1; i++){
        cout << left[i-1]*right[i+1] << " ";
    }
    cout << left[n-2] << " ";
}

Output:

Explanation:

This solution also addresses the issue through the utilization of two arrays, denoted as left and right. The algorithm consists of four for loops, with the initial one dedicated to setting all elements of both arrays left and right to 0. Subsequently, a second loop calculates the prefix product for each element. Following this, a third loop computes the suffix product of each element, and finally, the last loop combines the prefix and suffix products based on the current element.

Method 4: Using log and antilog

Let's consider a scenario to showcase the product array problem using logarithms and antilogarithms in the C++ programming language:

#include<iostream>
#include<cmath>
#define EPS 1e-9
using namespace std;
double calculateAntilog(double x) {
    double antilog = EPS + pow((long double)10.0, x);
    return antilog;
}
int main(){
    int n = 5;
    int nums[n] = {1,2,3,4,5};
    long double mul = 0;
    for (int i = 0; i < n; i++){
        mul += (long double)log10(nums[i]);
    }
    for(int i=0; i<n; i++){
        cout << calculateAntilog(mul - log10(nums[i])) <<" ";
    }

}

Output: