How to deal with Zeroes in a multiplication problem?

Problem is here, has to deal with Zeroes. They can be tricky: https://leetcode.com/problems/product-of-the-last-k-numbers/

1352. Product of the Last K Numbers
Medium
Implement the class ProductOfNumbers that supports two methods:
1. add(int num)
  • Adds the number num to the back of the current list of numbers.
2. getProduct(int k)
  • Returns the product of the last k numbers in the current list.
  • You can assume that always the current list has at least k numbers.
At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.

Example:
Input
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]

Output
[null,null,null,null,null,null,20,40,0,null,32]

Explanation
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3);        // [3]
productOfNumbers.add(0);        // [3,0]
productOfNumbers.add(2);        // [3,0,2]
productOfNumbers.add(5);        // [3,0,2,5]
productOfNumbers.add(4);        // [3,0,2,5,4]
productOfNumbers.getProduct(2); // return 20. The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8);        // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 4 * 8 = 32 

Constraints:
  • There will be at most 40000 operations considering both add and getProduct.
  • 0 <= num <= 100
  • 1 <= k <= 40000
The approach is going to be to keep a list of multiplication terms for every term i, from 0..i. Then to find the last k, simply do a last/last[len-k-1]. But no so fast..
Having the zeroes all over complicate things a bit. For instance, if you follow this approach and the very first item is a zero, everything turns into a zero. So you need to be careful and do not ever multiply by zero. Keep track of where the zeroes are, with an index (or indexes), but don't multiply by then. When it comes to returning the product, you can still do in O(1)-time if you know where the zeroes (or the latest zero) are. Code is below, cheers, ACC.


public class ProductOfNumbers
{
    private List<int> listProduct = null;
    private int latestZeroPosition;
    public ProductOfNumbers()
    {
        listProduct = new List<int>();
        latestZeroPosition = -1;
    }

    public void Add(int num)
    {
        if (num == 0)
        {
            latestZeroPosition = listProduct.Count;
            listProduct.Add(0);
        }
        else
        {
            if (listProduct.Count == 0 || listProduct.Last<int>() == 0)
            {
                listProduct.Add(num);
            }
            else
            {
                listProduct.Add(num * listProduct.Last<int>());
            }
        }
    }

    public int GetProduct(int k)
    {
        if (latestZeroPosition >= listProduct.Count - k) return 0;
        if (listProduct.Count - k - 1 < 0 || listProduct[listProduct.Count - k - 1] == 0) return listProduct.Last<int>();
        return listProduct.Last<int>() / listProduct[listProduct.Count - k - 1];
    }
}

Comments

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons