# Untitled

Sep 17th, 2023
807
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. n = int(input())
2. s = input()
3. x = int(s, 2)
4. g = 0
5. for i in s:
6.     if i == '1':
7.         g += 1
8. if g == 1:
9.     for i in s:
10.         if i == '1':
11.             print(0)
12.         else:
13.             print(1)
14.     exit(0)
15. if g == 0:
16.     print("1\n" * n)
17.     exit(0)
18. a = x % (g - 1)
19. ap = 1
20. c = x % (g + 1)
21. cp = 1
22. ans = []
23. shit = [0]
24. for i in range(1, 200100):
25.     shit.append(0)
26.     k = 1
27.     while k <= i:
28.         if i & k:
29.             shit[i] += 1
30.         k *= 2
31. for i in range(n - 1, -1, -1):
32.     if s[i] == '0':
33.         b = (c + cp) % (g + 1)
34.     else:
35.         b = (a - ap) % (g - 1)
36.     cnt = 1
37.     while True:
38.         h = shit[b]
39.         if h == 0:
40.             ans.append(cnt)
41.             break
42.         cnt += 1
43.         b %= h
44.     ap = 2 * ap % (g - 1)
45.     cp = 2 * cp % (g + 1)
46. for i in range(len(ans) - 1, -1, -1):
47.     print(ans[i])
48.