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(n2). 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()