How to Compute the Product of Last K elements in Array using the

  • 时间：2020-09-10 13:27:27
  • 分类：网络文摘
  • 阅读：115 次

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

1
2

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

Output

1

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

Explanation

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

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 
 
Hints:
Keep all prefix products of numbers in an array, then calculate the product of last K elements in O(1) complexity.
Hide Hint 2
When a zero number is added, clean the array of prefix products.
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 

Hints:
Keep all prefix products of numbers in an array, then calculate the product of last K elements in O(1) complexity.
Hide Hint 2
When a zero number is added, clean the array of prefix products.

Constraints:
There will be at most 40000 operations considering both add and getProduct.
0 <= num <= 100
1 <= k <= 40000

Bruteforce Algorithm to Compute the Last K Products of Array

Probably the easiest solution is to apply the bruteforce algorithm. To add a number, we use the append method of the list. And to get the product of the Last K elements, we can use array slicing and the reduce function from functools.

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

from functools import reduce
 
class ProductOfNumbers:
    def __init__(self):
        self.data = []
 
    def add(self, num: int) -> None:
        self.data.append(num)
 
    def getProduct(self, k: int) -> int:
        return reduce((lambda x, y: x * y), self.data[-k:], 1)
 
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)
from functools import reduce

class ProductOfNumbers:
    def __init__(self):
        self.data = []

    def add(self, num: int) -> None:
        self.data.append(num)

    def getProduct(self, k: int) -> int:
        return reduce((lambda x, y: x * y), self.data[-k:], 1)

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)

The Python code is inefficient for large data sets. The above solution may time out while the following equivalent C++ implementation may not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class ProductOfNumbers {
public:
    ProductOfNumbers() {
        
    }
    
    void add(int num) {
        data.push_back(num);
    }
    
    int getProduct(int k) {
        int s = 1;
        for (int i = 0; i < k; ++ i) {
            s *= data[data.size() - i - 1];
        }
        return s;
    }
private:
    vector<int> data;
};
 
/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
*/
class ProductOfNumbers {
public:
    ProductOfNumbers() {
        
    }
    
    void add(int num) {
        data.push_back(num);
    }
    
    int getProduct(int k) {
        int s = 1;
        for (int i = 0; i < k; ++ i) {
            s *= data[data.size() - i - 1];
        }
        return s;
    }
private:
    vector<int> data;
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
*/

We may use the std::accumulate() to rewrite the product part:

1
2
3

return std::accumulate(end(data) - k - 1, end(data), 1, [](auto &a, &b) {
   return a * b;
}); 
return std::accumulate(end(data) - k - 1, end(data), 1, [](auto &a, &b) {
   return a * b;
});

The bruteforce runs at O(1) time in add() and O(N) time in getProduct().

Compute the Last K Products of An Array using Prefix Products

Since all the inputs are integers, we can store the prefix product (the product of all the present numbers) while we add a new number to the list.

When we have a zero, we need to clear the array. The result would be the division between the last prefix sum and the prefix sum at [-k] position

See Python solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class ProductOfNumbers
    def __init__(self):
        self.data = [1]
 
    def add(self, num: int) -> None:
        if num == 0:
            self.data = [1]
        else:
            self.data.append(num * self.data[-1])
 
    def getProduct(self, k: int) -> int:
        if k >= len(self.data):
            return 0
        return self.data[-1] // self.data[ - k - 1]
 
# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)
class ProductOfNumbers
    def __init__(self):
        self.data = [1]

    def add(self, num: int) -> None:
        if num == 0:
            self.data = [1]
        else:
            self.data.append(num * self.data[-1])

    def getProduct(self, k: int) -> int:
        if k >= len(self.data):
            return 0
        return self.data[-1] // self.data[ - k - 1]

# Your ProductOfNumbers object will be instantiated and called as such:
# obj = ProductOfNumbers()
# obj.add(num)
# param_2 = obj.getProduct(k)

And the C++ solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class ProductOfNumbers {
public:
    ProductOfNumbers() {
    }
    
    void add(int num) {
        if (num > 0) {
            data.push_back(num * data.back());
        } else {
            data = {1};
        }
    }
    
    int getProduct(int k) {
        return k < data.size() ? data.back() / data[data.size() - k - 1] : 0;
    }
private:
    vector<int> data{1};
};
 
/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */
class ProductOfNumbers {
public:
    ProductOfNumbers() {
    }
    
    void add(int num) {
        if (num > 0) {
            data.push_back(num * data.back());
        } else {
            data = {1};
        }
    }
    
    int getProduct(int k) {
        return k < data.size() ? data.back() / data[data.size() - k - 1] : 0;
    }
private:
    vector<int> data{1};
};

/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * ProductOfNumbers* obj = new ProductOfNumbers();
 * obj->add(num);
 * int param_2 = obj->getProduct(k);
 */

The prefix product algorithm brings the complexity of the getProduct() method down to O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
数学题:把圆柱平均分成若干份后拼成一个长方体　 奥数题:甲乙两地中间有一座山岭　 奥数题:一份工作按计划的时间算　 简便计算题：1997÷(1997+1997/1998)+(1/1999)　 数学题:在比例尺1：5000的图纸上　 2014年是平年还是闰年　 数学题:在11次红灯变绿灯之间的黄灯亮起中　 奥数题:从这两堆煤中分别运走同样的吨数后　 数学题:用4cm长的线段表示实际距离1200km　 数学题:一根圆柱形木头小明的爸爸将它锯成4段　
评论列表
添加评论