Header Ad

HackerEarth Special bits problem solution

In this HackerEarth Special bits problem solution There are T test cases. Each test case contains the following:

  1. You are given three integers L and R that denote a range and k. Your task is to find a number in between the range L to R (inclusive) which has a set bit count as k.
  2. If there are multiple such numbers present in the range, print the minimum among such numbers. If no number satisfies the above condition, print -1.


HackerEarth Special bits problem solution


HackerEarth Special bits problem solution.

#include<bits/stdc++.h>
typedef long long ll;
typedef double ld;
#define vll vector<ll>
#define pll pair<ll ,ll >
#define vllp vector< pll >
#define mp make_pair
#define pb push_back
#define MOD 1000000007
#define endl "\n"
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define F first
#define S second
#define MAX 1000000007
using namespace std;

bool is_true(string s, ll r)
{
ll l = 0;
ll po = 1;
for (int i = 61; i >= 0; i--)
{
if (s[i] == '1')
l += po;
po *= 2;
}
if (l <= r)
return true;
return false;
}
ll to_long(string s)
{
ll l = 0;
ll po = 1;
for (int i = 61; i >= 0; i--)
{
if (s[i] == '1')
l += po;
po *= 2;
}
return l;
}
ll more_bit(ll l, ll r, ll k, ll l_bits)
{
string sl = bitset<62>(l).to_string();
for (int i = 61; i >= 0; --i)
{
if (sl[i] == '0')
{
sl[i] = '1';
l_bits++;
}
if (is_true(sl, r) && l_bits == k)
return to_long(sl);
}
return -1;
}
ll less_bit(ll l, ll r, ll k, ll l_bits)
{
ll co = 0;
string sl = bitset<62>(l).to_string();
for (int i = 61; i >= 0; i--)
{
if (sl[i] == '1')
co++;
if (sl[i] == '0')
{
string s = sl;
s[i] = '1';
for (int j = i + 1; j < 62; ++j)
{
s[j] = '0';
}
if (is_true(s, r) && l_bits - co + 1 == k)
return to_long(s);
if (is_true(s, r) && l_bits - co + 1 < k)
return more_bit(to_long(s), r, k, l_bits - co + 1);
}
}
return -1;
}
ll fun(ll l, ll r, ll k)
{
string sl = bitset<62>(l).to_string();
string sr = bitset<62>(r).to_string();
int set_bit = 0;
for (int i = 0; i < 62; ++i)
{
if (sl[i] != sr[i])
break;
if (sl[i] == '1')
set_bit++;
}
if (set_bit > k)
return -1;
int l_set_bit = 0;
for (int i = 0; i < 62; ++i)
{
if (sl[i] == '1')
l_set_bit++;
}
if (l_set_bit < k)
{
return more_bit(l, r, k, l_set_bit);
}
if (l_set_bit == k)
return l;
return less_bit(l, r, k, l_set_bit);
}
void solve() {
ll n;
ll l, r, k;
cin >> l >> r >> k;
cout << fun(l, r, k) << endl;
}

int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}


Second solution

B = 60
t = int(input())
while t > 0:
t -= 1
l, r, k = map(int, input().split())
for i in range(B):
if l >> i & 1:
k -= 1
if k < 0:
where = 0
while k < 1 or (l >> where & 1):
if l >> where & 1:
l ^= 1 << where
k += 1
where += 1
l |= 1 << where
k -= 1

if k > 0:
for i in range(B):
if not (l >> i & 1):
k -= 1
l |= 1 << i
if not k:
break
print(l if l <= r else -1)


Post a Comment

0 Comments