Hello Folks! This is my very second note. So lets get started. Suppose a problem in which you have to find the sum of nos. from 1 till n (1<=n<=10^5) whose signed bits are even or equal to particular no. k . Now one simple approach is to run obviously from 1 till n and for each no. find the signed bits using the approach guided in @hackerearth's practice corner of bit manipulation. (Click here to get to that page)

Solution using basic approach or Without Memorisation

int arr[]=new int[n+1];

//arr of n+1 size where each element is initialized with 0.

arr[0]=0;

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

//**n**

{

int count=0;

while(j!=0)

//**logn**

{

int j=i&(i-1);

//**logn** // taking bitwise & of two no.s For eg:- 15&14 is equal to 14.

count++;

//**logn**

}

arr[i]=count;

//**1**

/*check your conditions like whatever the ques has given.

Like if(arr[i]==2)

sum+=i; where sum is initialised with 0.

*/

}

So the final complexity will be =log1+log2+log3+log4+log5+...+logn (where log is log base 2) is approximately greater than O(n).

So I have a better approach where we use space to save our time!

The approach is like this :-

int arr[]=new int[n+1];

//arr of n+1 size where each element is initialized with 0.

arr[0]=0;

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

//**n**

{

int j=i&(i-1);

//**1**

// taking bitwise & of two no.s For eg:- 15&14 is equal to 14.

arr[i]=1+(arr[j]);

//**1**

/*check your conditions like whatever the ques has given.

Like if(arr[i]==2)

sum+=i; where sum is initialised with 0.

*/

}

In the above code, you may see that the solution is running for n times and the cost of the expressions inside the loop is O(1) so the final complexity will be O(n)+O(1)+O(1) will be equal to O(n).

Hope you may find the logic easily.

⇮
⇩