can anyone help me to CodeChef: Practical coding for everyone in Python?
I hope this might help you
I used count_one function to count the # of 1’s set in number
def count_one(n):
c=0
while (n):
n=n&(n-1)
c=c+1
return c
for i in range(int(input())):
n=int(input())
ans=0
for p in range(1,(n+1)):
ans=ans+p*count_one(p)
print(ans)
I solved it by constructing a recurrence for the sum . First lets solve the problem when N is a power of 2 minus 1. You can solve it for any value of N once you solve for powers of 2 minus 1.
b_i denotes the number of 1’s in binary representation of i.
S(N) = \sum i * b_i
T(N) = \sum b_i
If you notice the binary representation of numbers from \frac{N}{2} to N - 1 , it is same as the numbers from 0 to \frac{N}{2} - 1 with an extra 1 added to the front . We can exploit this fact to create the sum.
Let N' = \frac{N}{2} + 1
S(N) = S(N' - 1) + [((N'+ 0)*(b_0 + 1))+((N' + 1)*(b_1 + 1))\ \ ...\ \ ((N' + N')*(b_{N'} + 1))]
S(N) = S(N' - 1) + N'*T(N') + N'^{2} + S(N' - 1) + \frac{N' * (N' - 1)}{2}
T(N) = 2*T(N') + N'
Hence you can compute the value of S(N) , T(N) in O(log(N)) .
For solving for any value of N you need to split it into smaller powers of 2 and combine the results .
Our AC
(https://www.codechef.com/viewsolution/15255799)
Thanks for your help but TLE will be result of the above code as it takes much time for n = 10**8