Can someone help me in solving this problem??
The problem editorial is tough to understand. It can be solved using hashmap +prefix sum but I am not able to the get the pattern /observation
Problem Link :Problem - 1398C - Codeforces
Consider an array = [1,0,2,1,1] , if we subtract each element by 1 then array become [0,-1,1,0,0] then the number of good subarrays is equal to the number of subarrays whose sum is 0. This is because consider a subarray of length x, and its sum suppose m , we already subtract x from it initially by subtracting each element by 1, it means we subtract its length from it. Then the sum equal to its length if and only if subarray sum is 0.
Mathematically
Sum = Length
Sum - Length = 0
we already subtract the length from sum initially . It means the subarray sum must be zero.
Hope its helpful.
1 Like
Thanks Captain !!! I got it .