Array Product Except Self Index Value

Given an array of integers, return a new array such that each element at the index i of the new array is the product of all the numbers in the original array except the one at i.

Example:

Input:  arr[]={1,2,3,4,5}
Output: 120,60,40,30,24

Approach 1: Using Two For Loops

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> findArrayProductExceptSelf(vector<int> arr)
{
    vector<int> res;

    //find the size of array
    int n = arr.size();

    //iterate for each index
    for (int i = 0; i < n; i++)
    {

        //initialize the product variable
        int product = 1;
        for (int j = 0; j < n; j++)
        {

            //if index is same then
            //continue
            if (i == j)
            {
                continue;
            }

            //update the product
            else
            {
                product = product * arr[j];
            }
        }

        //add into the result array
        res.push_back(product);
    }

    //return the result array
    return res;
}
int main()
{
    vector<int> arr = {1, 2, 3, 4, 5};

    vector<int> res = findArrayProductExceptSelf(arr);

    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i] << " ";
    }

    return 0;
}

//Time Complexity: O(n^2)
//Space Complexity: O(1)

Approach 2: Using Memory

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> findArrayProductExceptSelf(vector<int> arr)
{
    int n = arr.size();

    //make left and right array
    int left[n + 1];
    int right[n + 1];

    left[0] = 1;

    //find the product of elements
    //left of index i
    for (int i = 1; i < n; i++)
    {
        left[i] = arr[i - 1] * left[i - 1];
    }
    
    right[n - 1] = 1;

    //find the product of elements
    //right of index i
    for (int i = n - 2; i >= 0; i--)
    {
        right[i] = right[i + 1] * arr[i + 1];
    }
    vector<int> ans;
    for (int i = 0; i < n; i++)
        ans.push_back(left[i] * right[i]);
    return ans;
}
int main()
{

    vector<int> arr = {1, 2, 3, 4, 5};

    vector<int> res = findArrayProductExceptSelf(arr);

    for (int i = 0; i < res.size(); i++)
    {
        cout << res[i] << " ";
    }

    return 0;
}

//Time Complexity :O(n)
//Space Complexity: O(n)