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: 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. 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. #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 = 60t = 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