Hacker rank doubts

#1

Can u tell me what shoud be approach of this problem.

#2

We have N^2 options, one every possible i and j. So, our answer will be total valid pairs divided by . N^2 Now, we need to count the valid pairs.

We traverse over i=1 to N If is 1 , we will count how many valid j pairs are. We need to know how many 1 s there are between indices i-k and i+k (inclusive).

We will keep a prefix array pre where pre[i] stores the number of 1 s occuring till the 'th index ( pre can be precalculated in O(N) time). To know number of 1 s between any a and b (both inclusive), pre[b]-pre[a-1] will give the answer.

Reference Code

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.