A Product Array Puzzle | GeeksforGeeks

Related: LeetCode 238 - Product of Array Except Self
Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division operator and in O(n).

1) Construct a temporary array left[] such that left[i] contains product of all elements on left of arr[i] excluding arr[i].
2) Construct another temporary array right[] such that right[i] contains product of all elements on on right of arr[i] excluding arr[i].
3) To get prod[], multiply left[] and right[].

    void productArray(int arr[], int n)

    {

        // Initialize memory to all arrays

        int left[] = new int[n];

        int right[] = new int[n];

        int prod[] = new int[n];

        int i, j;

        /* Left most element of left array is always 1 */

        left[0] = 1;

        /* Rightmost most element of right array is always 1 */

        right[n - 1] = 1;

        /* Construct the left array */

        for (i = 1; i < n; i++)

            left[i] = arr[i - 1] * left[i - 1];

        /* Construct the right array */

        for (j = n - 2; j >= 0; j--)

            right[j] = arr[j + 1] * right[j + 1];

        /* Construct the product array using

           left[] and right[] */

        for (i = 0; i < n; i++)

            prod[i] = left[i] * right[i];

        /* print the constructed prod array */

        for (i = 0; i < n; i++)

            System.out.print(prod[i] + " ");

        return;

    }

The above method can be optimized to work in space complexity O(1).

    void productArray(int arr[], int n)

    {

        int i, temp = 1;

         

        /* Allocate memory for the product array */

        int prod[] = new int[n];

        /* Initialize the product array as 1 */

        for(int j=0;j<n;j++)

            prod[j]=1;

        /* In this loop, temp variable contains product of

           elements on left side excluding arr[i] */

        for (i = 0; i < n; i++)

        {

            prod[i] = temp;

            temp *= arr[i];

        }

        /* Initialize temp to 1 for product on right side */

        temp = 1;

        /* In this loop, temp variable contains product of

           elements on right side excluding arr[i] */

        for (i = n - 1; i >= 0; i--)

        {

            prod[i] *= temp;

            temp *= arr[i];

        }

        /* print the constructed prod array */

        for (i = 0; i < n; i++)

            System.out.print(prod[i] + " ");

        return;

    }

http://www.geeksforgeeks.org/construct-an-array-from-xor-of-all-elements-of-array-except-element-at-same-index/

Given an array A[] having n positive elements. The task to create another array B[] such as B[i] is XOR of all elements of array A[] except A[i].

void constructXOR(int A[], int n)

{

    // calculate xor of array

    int XOR = 0;

    for (int i=0; i < n; i++)

        XOR ^= A[i];

    // update aaray

    for (int i=0; i < n; i++)

        A[i] = XOR ^ A[i];

}

Read full article from A Product Array Puzzle | GeeksforGeeks