Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Special bits problem solution

YASH PAL, 31 July 2024
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)
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes