PROBLEM LINK:
Author: Rahul Sharma
Tester: Sumukh Bhardwaj
Editorialist: Rahul Sharma
DIFFICULTY:
Easy
PREREQUISITES:
Bits, Observation, Math
PROBLEM:
Given two integers N and K. For the binary representation of N following transformation is applied
The most significant set bit is moved to the last and new N is computed.
This transformation is done K times. Can you predict value of N after K transformations ?
EXPLANATION:
Let number of set bits in number N be \alpha and most significan set bit be \beta. At each transformation we are move most significant bit to last
This is equivalent to resetting the most significant bit, shifting all bits to left by 1 and setting the last bit. Thus a new N can be computed as
N = ((N - 2^\beta) << 1) + 1
Subtask #1:
If we compute N for K times using above equation we will eventually get the answer. But it will only pass subtask #1.
Subtask #2:
If you observe carefully the minimum N will be reached after apply transformation \alpha times because after than all set bits will be on extreme right and applying the transformation will not generate any new number. Thus if K > \alpha we can directly give answer as 2^\alpha-1.
COMPLEXITIES:
Time Complexity: O(logN) for each test case
Space Complexity: O(1) for each test case
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
long long int countSetBits(long long int n)
{
long long int i = 0, count = 0;
while(n >= (1ULL<<i))
{
if ((n & (1ULL<<i)))
count++;
i++;
}
return count;
}
long long int setBitNumber(long long int n)
{
long long int k = (long long int)(log2(n));
return 1ULL << k;
}
int main()
{
long long int n, setBits, setBitNum, minVal = 0, ans = 0, k;
cin >> n >> k;
setBits = countSetBits(n);
minVal = pow(2ULL,setBits) - 1;
while (k && n > minVal)
{
setBitNum = setBitNumber(n);
n = ((n - setBitNum) << 1ULL) + 1;
k--;
}
cout << n;
return 0;
}