COUNTING BITS

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

Program :

#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;

}