BBITS - Editorial

editorial
,
1

PROBLEM LINK:

Contest

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