Accumulate Product

The accumulate product problem involves finding the product of all elements in a given range of an array. This is similar to range sum, but computes the product rather than sum.

Some example code:

Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// Compute product of [i, j]
int accumulateProduct(int[] nums, int i, int j) {
  
  int product = 1;
  
  for(int k=i; k<=j; k++) {
    product *= nums[k];
  }
  
  return product;
}

int[] nums = {1, 2, 3, 4, 5};
int prod = accumulateProduct(nums, 1, 3); // returns 2 * 3 * 4 = 24

C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// Compute product of [i, j]
int accumulateProduct(vector<int>& nums, int i, int j) {

  int product = 1;

  for(int k=i; k<=j; k++) {
    product *= nums[k]; 
  }

  return product; 
}

vector<int> nums{1, 2, 3, 4, 5}; 
int prod = accumulateProduct(nums, 1, 3); // returns 24

Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# Compute product of [i, j]
def accumulate_product(nums, i, j):

  product = 1
  
  for k in range(i, j+1):
    product *= nums[k]

  return product

nums = [1, 2, 3, 4, 5]  
prod = accumulate_product(nums, 1, 3) # returns 24

The key steps are:

  1. Initialize product to 1
  2. Iterate through range, multiplying each element to product
  3. Return final product

This allows efficiently finding the product of a contiguous subarray. Useful for combinatorics and other math problems.

The concept of Accumulate Product is similar to Accumulate Sum, but with multiplication instead of addition. You keep a running product of a sequence of numbers, often within a loop. The accumulated product typically starts at 1 (because 1 is the identity for multiplication), and every number in the sequence gets multiplied to this running product.

Here’s an example in Python:

1
2
3
4
5

numbers = [2, 3, 4, 5]
product = 1
for num in numbers:
    product *= num
print(product)  # Output: 120

This will keep multiplying each number in the numbers list to the product variable, which accumulates the total product.

In Python, the built-in functools.reduce function, which applies a binary function (in this case, operator.mul) to all items of an iterable in a cumulative way, can also be used for this purpose:

1
2
3
4
5
6

from functools import reduce
import operator

numbers = [2, 3, 4, 5]
product = reduce(operator.mul, numbers, 1)
print(product)  # Output: 120

This does the same thing: it multiplies all the numbers in the list together. The third argument to reduce (1 in this case) is a starting value that is used as the initial accumulator.

Here are some problems that involve “Accumulate Product”:

  1. LeetCode #238: Product of Array Except Self: In this problem, you are asked to output an array where each element is the product of all the other elements in the input array. To solve this problem efficiently, you need to use the concept of accumulating the product from both the left and the right of each position.

  2. LeetCode #152: Maximum Product Subarray: Here, you need to find the contiguous subarray within an array that has the largest product. You’ll use a dynamic programming approach to keep track of the maximum product you can get at each position, considering both positive and negative products due to negative numbers in the array.

  3. LeetCode #42: Trapping Rain Water: While this problem is more about finding the trapped water in an elevation map, the solution involves two accumulators keeping track of the highest bar from the left and the right, similar to a product accumulation.

  4. LeetCode #50: Pow(x, n): This problem asks you to implement the pow(x, n) function, which calculates x raised to the power n. Efficient solutions often involve a binary exponentiation method, which is a form of accumulating the product while halving the exponent.

These problems can’t be solved just by accumulating a product. They require a mix of other techniques as well, such as dynamic programming, two-pointers, or divide-and-conquer. The accumulation of the product is just one aspect of the solutions.