COUNTING BITS

• Problem Description

  
  "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
  "
  

• Test Case 1

  
  Input (stdin)

  1
  
  3
  
  

  Expected Output

  4

• Test Case 2

  
  Input (stdin)

  1
  
  7
  
  

  Expected Output

  12

Solution

#include <stdio.h>

static int arr[1001];

int converter(int n,int sum)

{

sum+=n%2;

n=n/2;

if(n==0)

return sum;

else

return converter(n,sum);

}

void binary()

{

int i,t,j;

for(i=1;i<1001;i++)

{

if(arr[i]==0)

{

t=converter(i,0);

arr[i]=t;

for(j=2;i*j<=1001;j*=2)

arr[i*j]=t;

}

}

}

int main()

{

int t;

scanf("%d",&t);

binary();

while(t--)

{

int n,i,ans=0;

scanf("%d",&n);

for(i=1;i<=n;i++)

ans+=arr[i];

printf("%d\n",ans);

}

  return 0;

}