BITS - Counting Bits

no tags 

Given N, if we write all numbers from 1 to N (both inclusive) in binary what is the count of 1s I have written.
For example, if N=3,
I will write down:
1
10
11
Therefore, a total of 4 ones.

Input Format:

First line contains, T, the number of testcases. Each testcase consists of one integer per line denoting N.

Output Format:

Print the required answer.

Constraints:

1 ≤ T ≤ 1000
1 ≤ N ≤ 1000

Sample Input:

1
3

Sample Output:

4


Problem Setter: Lalit Kundu

Solve harder version here: http://www.spoj.com/problems/BIT2 


hide comments
ivar.raknahs: 2014-02-22 15:34:55

easy with python

Anubhav Balodhi : 2014-02-16 08:38:12

The very basic of programming...

Rishav Goyal: 2014-02-13 04:50:55

try this after BITS , http://www.spoj.com/problems/BIT2

Last edit: 2014-02-08 15:35:00
Rishav Goyal: 2014-02-13 04:50:55

would be better raise the limit ~10^9 or more than that.

Aravindan Chandrasekaran: 2014-02-13 04:50:55

But I am getting WA ?

: 2014-02-13 04:50:55

Last edit: 2014-02-27 07:38:45
Jacob Plachta: 2014-02-13 04:50:55

I'm pretty sure that there are already problems on SPOJ that ask exactly this (or similar things), with larger bounds (like 10^9).
--ans(francky)--> I'm sure too. My search box isn't functional, so I can't give a link. Problem moved to tutorial.

Last edit: 2014-02-02 16:10:52
suryadev: 2014-02-13 04:50:55

Anybody is having better solution than O(N) or O(NlogN) ?

Bhavik: 2014-02-13 04:50:55

@aravindan: yes

Aravindan Chandrasekaran: 2014-02-13 04:50:55

Answer for 1000 is 4938 right ?


Added by:darkshadows
Date:2014-01-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64