Product Array Puzzle Problem in Java
Considering that we have an array a[] consisting of n integers, create a product array prod[] of the same size so that product[i] is the product of all the elements in a[] except a[i].
Example 1:
Input:
int a[] = { 1, 10, 5 }
Output:
The product array elements are given by 50 5 10.
Explanation:
Given the array is { 1, 10, 5 }. Perform the product of the other elements except a[i], then,
a[1] * a[2] = 10 * 5 = 50
a[0] * a[2] = 1 * 5 = 5
a[0] * a[1] = 1 *10 = 10
Hence, the output printed as the product array elements are 50 5 10.
Example 2:
Input:
int a[] = { 6, 4, 10, 3, 5 }
Output:
The product array elements is given by 600 900 360 1200 720.
Explanation:
Given the array is {6, 4, 10, 3, 5}. Perform the product of the other elements except a[i], then,
a[1] * a[2] * a[3] * a[4] = 4 * 10 * 3 * 5 = 600
a[0] * a[2] * a[3] * a[4] = 6 * 10 * 3 * 5 = 900
a[0] * a[1] * a[3] * a[4] = 6 * 4 * 3 * 5 = 360
a[0] * a[1] * a[2] * a[4] = 6 * 4 * 10 * 5 = 1200
a[0] * a[1] * a[2] * a[3] = 6 * 4 * 10 * 3 = 720
Hence the output printed as the product array elements are 600 900 360 1200 720.
Approach: Using Prefix and Suffix Multiplication
Create two extra spaces that is, two additional arrays to hold the product of all the array elements from the beginning to that index and an additional array to hold the product of all the array elements at the end of the array to that index.
To obtain the product that excludes that index, multiply the suffix product up to index i+1 by the prefix product up to index i-1.
Algorithm:
Step 1: Create two arrays, prefix and suffix, of length n, or the length of the original array. Initialise prefix[0] = 1 and suffix[n-1] = 1 for both arrays and create a second array to hold the product.
Step 2: Go from the second index to the end of the array in this step.
Step 3: Store the product up to index i-1 from the array's beginning by updating prefix[i] for each index as prefix[i] = prefix[i-1] * array[i-1].
Step 4: Go from the second-last index to the start of the array.
Step 5: Store the product up to the i+1 index from the array's end by updating suffix[i] for each index i as suffix[i] = suffix[i+1] * array[i+1].
Step 6: Go through the array from beginning to end.
Step 7: The result, which is the product of all array elements except that one, will be prefix[i] * suffix[i] for each index i.
Implementation:
FileName: PrefixSuffixProductArray.java
import java.io.*;
import java.util.*;
public class PrefixSuffixProductArray
{
// Function for printing the product array for a specified size-n array a[]
void product(int a[], int n)
{
// Base case
if (n == 1)
{
System.out.print(0);
return;
}
// Set up each array's memory initially
int leftele[] = new int[n];
int rightele[] = new int[n];
int pro[] = new int[n];
int i, j;
// The leftmost entry element in the left array is always 1.
leftele[0] = 1;
// The rightmost entry element in the left array is always 1.
rightele[n - 1] = 1;
// Creation of the left array
for (i = 1; i < n; i++)
leftele[i] = a[i - 1] * leftele[i - 1];
// Creation of the right array
for (j = n - 2; j >= 0; j--)
rightele[j] = a[j + 1] * rightele[j + 1];
// Creation of the product array by using leftele[] and rightele[]
for (i = 0; i < n; i++)
pro[i] = leftele[i] * rightele[i];
// display the created product array
for (i = 0; i < n; i++)
System.out.print(pro[i] + " ");
return;
}
public static void main(String[] args)
{
PrefixSuffixProductArray obj = new PrefixSuffixProductArray();
int a[] = { 6, 4, 10, 3, 5 };
int n = a.length;
System.out.println("The product array elements is given by ");
obj.product(a, n);
}
}
Output:
The product array elements are given by
600 900 360 1200 720
Complexity Analysis:
The above technique has an O(n) time complexity since the array must be traversed three times, and an O(n) space complexity because two additional arrays and one array are required to hold the output.
Approach: Efficient Method
The prefix and suffix were stored in two additional arrays in the previous solution; however, in this approach, the prefix and suffix are stored in the output array, also known as the product array. Hence, a lesser amount of space is needed.
Algorithm:
Step 1: Create an array product, set its initial value to 1, and set the variable temp to 1.
Step 2: Go through the array from beginning to end.
Step 3: For each index of i, update product[i] for each index by using the formulas product[i] = temp and temp * array[i], which stores the product up to the i-1 index from the array's beginning.
Step 4: set temp = 1 and go from the last index to the beginning of the array.
Step 5: For each index of i, update product[i] for each index as product[i] = product[i] * temp and temp = temp * array[i], meaning that I multiply by the product up to i+1 index from the array's end.
Step 6: Printing the product array is the final step.
Implementation:
FileName: EfficientProductArray.java
import java.io.*;
import java.util.*;
public class EfficientProductArray
{
void product(int a[], int n)
{
// Base case
if (n == 1)
{
System.out.print("0");
return;
}
int i, temp = 1;
// Allocate memory available for the product array.
int pro[] = new int[n];
// Set the product array's initial value to 1.
for (int j = 0; j < n; j++)
pro[j] = 1;
// The product of all the elements on the left side,
// except a[i], is stored in the temp variable of this loop.
for (i = 0; i < n; i++)
{
pro[i] = temp;
temp *= a[i];
}
// Set the product's temp to 1 on the right side.
temp = 1;
// The temp variable in this loop holds the product of
// the elements on the right side, excluding a[i].
for (i = n - 1; i >= 0; i--)
{
pro[i] *= temp;
temp *= a[i];
}
// display the created product array
for (i = 0; i < n; i++)
System.out.print(pro[i] + " ");
return;
}
public static void main(String[] args)
{
EfficientProductArray obj = new EfficientProductArray();
int a[] = { 6, 4, 10, 3, 5 };
int n = a.length;
System.out.println("The product array elements is given by ");
obj.product(a, n);
}
}
Output:
The product array elements are given by
600 900 360 1200 720
Complexity Analysis:
In the above technique, the space complexity is given by O(n); the time complexity is constant because only one traversal of the original array is required. Since the product array is still required, the space complexity is still O(n) even after the extra arrays are eliminated.