# PROBLEM LINK:

* Author:* Rahul Sharma

* Tester:* Sumukh Bhardwaj

* Editorialist:* Rahul Sharma

# DIFFICULTY:

Simple

# PREREQUISITES:

Bits, Simple math

# PROBLEM:

Given two positive integers N and K. A series is defined as

T(N) = T(N-1) + 2*oneBits(K) + 3*zeroBits(K)

T(1) = 1

where oneBits(K) is count of set bits in K

zeroBits(K) is count of zero bits in K between most significant set bit and least significant bit.

Find N^{th} term of series.

# QUICK EXPLANATION:

It is an arithmetic progression with first term as 1 and common difference 2*oneBits(K) + 3*zeroBits(K). Find one and zero bits

# EXPLANATION:

For the given number K count the number of zero and one bits. Check if the i^{th} bit is set or not and increment the count0 and count1 accordingly as follows:

```
if ((1<<i) & K):
count1+=1
else
count0+=1
```

Repeat above procedure for all valid i's

**Subtask #1:**

Let ans=1. Now loop through 2 to N and update ans as

ans = ans + 2*count1 + 3*count0

**Subtask #2:**

Since it is an arithmetic progression with common difference as

diff = 2*count1 + 3*count0

Thus answer can be directly given as

ans = 1 +(N-1)*diff

*Note: We used shift operator to calculate set and non-set bits because it is more efficient as compared to using modulo and division operator for the same.*

# COMPLEXITIES:

**Time Complexity:** O(logK) for each test case

**Space Complexity:** O(1) for each test case

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int n, k, i;
cin >> n >> k;
long long int count1, count0;
count1 = 0;
count0 = 0;
i = 0;
while(k >= (1<<i))
{
if (k & (1<<i))
count1++;
else
count0++;
i++;
}
long long int diff = 2*count1 + 3*count0;
long long int ans = 1 + (n-1)*diff;
cout << ans;
return 0;
}
```