HackerEarth Special bits problem solution

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 = 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