Python Help for INSQ17R

general
, , , ,
1

can anyone help me to https://www.codechef.com/INQU2017/problems/INSQ17R in Python?

2

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)
3

Thanks for your help but TLE will be result of the above code as it takes much time for n = 10**8

4

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)
2 Likes