PROBLEM LINK:
Author: Misha Chorniy
Tester: Jingbo Shang
Editorialist: Pushkar Mishra
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Given an array, we have to report the number of subarrays such that the product of all numbers in that subarray is equal to the sum of all numbers in that subarray.
EXPLANATION:
The problem is very direct given the size of the input array. Since n \leq 50, we can directly iterate over the subarrays and calculate product and sum. The editorialist’s solution is very clear in describing the approach. Below is the pseudo-code of the same:
function get_ans(input_array[n])
{
int count = 0;
for(i = 1 to n)
{
int sum = 0, product = 1;
for(j = i down_to 1)
{
//considering all subarrays ending at i.
sum = sum + input_array[j];
product = product*input_array[j];
if(sum == product)
count = count+1;
}
}
return count;
}
COMPLEXITY:
\mathcal{O}(n^2) per test case.