# LeetCode : 0238. Product of Array Except Self (array)
###### tags:`leetcode`

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <unordered_map>
using std::vector;
using std::unordered_map;
using namespace std;

class BaseVectorPrint {
    public:
        void BasePrint00(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << "[" <<num.at(i) << "]" << "; ";
            }
            cout << endl;
        }

        void BasePrint01(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << num[i] << "; ";
            }
            cout << endl;
        }

        void BasePrint02(vector<int>& num) {
            for (const auto &item : num) {
                cout << item << "; ";
            }
            cout << endl;
        }
        
        void TwoDimensionalPrint(vector<vector<int>> &num){
            for (int i = 0; i < num.size(); i++)
            {
                for (int j = 0; j < num[i].size(); j++)
                {
                    cout << "[" << num[i][j] << "]";
                }
                cout << endl;
            }
        }
};

class Solution01 {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> fromBegin(n);
        fromBegin[0]=1;
        vector<int> fromEnd(n);
        fromEnd[0]=1;
        
        for(int i=1;i<n;i++){
            fromBegin[i]=fromBegin[i-1]*nums[i-1];
            fromEnd[i]=fromEnd[i-1]*nums[n-i];
        }
        //total max List {320,320,320,320,320 }
        //example   List {  4,  5,  1,  8,  2 };
        //                  ↑ ↘ ↑ ↘ ↑ ↘ ↑ ↘
        //fromBegin List {  1,  4, 20, 20,160 }

        //example   List {  4,  5,  1,  8,  2 };
        //                   ↙ ↑ ↙ ↑ ↙ ↑ ↙
        //fromLast  List { 80, 16, 16,  2,  1 }

        //multiplicatiot { 80, 64,320, 40,160 }
        
        vector<int> res(n);
        for(int i=0;i<n;i++){
            res[i]=fromBegin[i]*fromEnd[n-1-i];
        }
        return res;
    }

    //time complexity O(n)
    //space complexity O(n)
};

class Solution02 {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        int Reverse_R = 1;

        vector<int> ans(n);
        ans[0] = 1;
        for(int i=1;i<n;i++){
            ans[i] = ans[i-1]*nums[i-1];
            // make Begin List;
        }

        for(int j = (n-1); j>=0; j--){
            // make End to Begin.
            ans[j] = ans[j]*Reverse_R;
            Reverse_R *= nums[j];
            // Reverse_R make End List 
        }

        return ans;
    }

    //time complexity O(n)
    //space complexity O(1)
};

int main(void)
{
    BaseVectorPrint printVector;
    Solution01 runfunc;

    vector<int> test01 = {  4,  5,  1,  8,  2 };
    vector<int> test02 = {  1,  2,  3,  4 };
    vector<int> test03 = { -1,  1,  0, -3,  3 };
    vector<int> ans ;

    ans = runfunc.productExceptSelf(test01);
    printVector.BasePrint00(ans);

    //printf("%d\n",input_Nums);
    printf("test\n");
    system("pause");
}

> Tip first (Begin) and last (end) is one nums
> Make Begin to end List
> Make End to Begin
> reduce space temp space reverse total num[n-i-1]*Reverse