BITS - Counting Bits
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
First line contains, T, the number of test cases. Each test case consists of one integer per line denoting N.
Output
Print the required answer.
Constraints
1 ≤ T ≤ 1000
1 ≤ N ≤ 1000
Example
Input: 1 3 Output: 4
Problem Setter: Lalit Kundu
Solve harder version here: 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 ? |
|
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).
|
|
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 |