Prefix Product

The prefix product of an array is an array where each element is the product of all elements to the left of it. For an array a[], the prefix product p[] is defined as:

p[0] = 1 (by convention) p[i] = p[i-1] * a[i-1]

Intuitively, p[i] contains the product of all prefix elements of a[] up to i.

Prefix products are useful for some array algorithms:

• Can calculate product of entire array in O(n) time
• Used to efficiently find product of elements except at index
• Help compute running averages and sums

Example in Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int[] arr = {3, 2, 5};

int[] p = new int[arr.length];
p[0] = 1; 

for(int i=1; i < arr.length; i++) {
  p[i] = p[i-1] * arr[i-1]; 
}

// p = {1, 3, 6} 

Example in C++:

1
2
3
4
5
6
7
8
9

vector<int> arr {2, 3, 4, 5};
vector<int> p(arr.size());
p[0] = 1;

for(int i=1; i < arr.size(); i++) {
  p[i] = p[i-1] * arr[i-1];
}

// p = {1, 2, 6, 24}

Example in Python:

1
2
3
4
5
6
7
8

arr = [1, 2, 3, 4]

p = [1] 

for i in range(1, len(arr)):
  p.append(p[-1] * arr[i-1])
  
# p = [1, 1, 2, 6]  

In summary, the prefix product of an array contains the product of all elements up to a given index. It can be calculated in linear time and enables efficient queries.

The concept of Prefix Product involves calculating the product of all the elements before a given index in an array. The prefix product at a given index ( i ) contains the product of all elements from index ( 0 ) to ( i-1 ). It can be particularly useful in solving problems that require information about the multiplication of elements preceding a certain position.

Solution

Java

1
2
3
4
5
6
7
8

public int[] prefixProduct(int[] arr) {
    int[] result = new int[arr.length];
    result[0] = 1;
    for(int i = 1; i < arr.length; i++) {
        result[i] = result[i - 1] * arr[i - 1];
    }
    return result;
}

C++

1
2
3
4
5
6
7
8

std::vector<int> prefixProduct(std::vector<int>& arr) {
    std::vector<int> result(arr.size());
    result[0] = 1;
    for(int i = 1; i < arr.size(); i++) {
        result[i] = result[i - 1] * arr[i - 1];
    }
    return result;
}

Python

1
2
3
4
5

def prefixProduct(arr):
    result = [1] * len(arr)
    for i in range(1, len(arr)):
        result[i] = result[i - 1] * arr[i - 1]
    return result

These code snippets initialize the result array with the value 1 at the 0th index, since no elements precede it. The subsequent values are filled in by multiplying the previous prefix product with the corresponding array element, thus accumulating the product for each index.

Tabular Representation

Input array: [2, 3, 4, 5]

In each iteration, the current Prefix Product is calculated by multiplying the previous Prefix Product with the current element in the input array. The final result array holds the Prefix Product for each element in the array.