 # BBITS - Editorial

Contest

Author: Rahul Sharma

Tester: Sumukh Bhardwaj

Editorialist: Rahul Sharma

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

Let ans=1. Now loop through 2 to N and update ans as
ans = ans + 2*count1 + 3*count0

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;
}
``````
1 Like