**DIFFICULTY:**

Medium

**PREREQUISITES:**

Fast Fourier Transformation

**PROBLEM:**

Alice and Bob are locked during Coronavirus. During the lockdown, Bob and Alice want to eat cake. So, they order online for the cake. They ordered N boxes of cake numbered 1 to N. As it was online order so they are cheated by the seller. Each box is either empty or contains cake. Bob wants to eat more cake so he comes up with a game. Winner of this game will eat more cake in comparison to the loser.

Bob define a distance dd, the difference of the indices between any pair of boxes. For every value of d from 0 to N−1, Alice has to count distinct pairs of boxes such that the distance between them is dd and both the boxes are non-empty(contains cake). Alice wants to win and asks you to help her.

**EXPLANATION:**

If we simply run a brute force then the solution takes O(n^{2}). The optimizes solution uses fast Fourier transformation. In the given problem, we are required to find all pairs of ones such that the distance between them d is and we have to perform this for d every from 0 to n - 1.

**TIME COMPLEXITY:**

O(nlogn)

**SOLUTIONS:**

## Setter's Solution

```
n=int(input())
s=input()
l=[]
for i in range(n):
c=0
j=0
while(j<n-i):
if(s[j]=='1' and s[i+j]=='1'):
c+=1
j+=1
l.append(c)
for i in l:
print(i,end=" ")
print()
```