Subarray with Target Product
Given an array of N integers and a target product K, find the number of contiguous subarrays whose product is exactly equal to K. The array may contain zeros and negative numbers. If K is zero, only subarrays containing at least one zero and no other non-zero elements will satisfy the condition if K is 0.
Input
The first line contains two integers N and K. The second line contains N integers representing the array elements.
Output
Print a single integer: the number of subarrays whose product is exactly K.
Constraints
1 <= N <= 200000 -10^9 <= array elements <= 10^9 -10^9 <= K <= 10^9
Example 1
4 12 2 3 1 4
1
The subarray [3, 1, 4] has product 12.
Example 2
5 0 1 2 0 4 5
9
There are 9 subarrays with product 0: [0], [2,0], [1,2,0], [0,4], [0,4,5], [2,0,4], [1,2,0,4], [2,0,4,5], [1,2,0,4,5].
Hints
Similar problems
- Count Elements with Equal NeighborsMedium
- Longest Subarray with At Most K Duplicate PairsMedium
- Count Matching PairsMedium
- Find the First Unique ElementMedium
- Distinct Elements in a Sliding WindowMedium
- Count Pairs with Equal ProductMedium
More topics: Arrays problems, Hash Map and Hashing problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 12 2 3 1 4
5 0 1 2 0 4 5