Maximum occurring integer in given ranges

Given numbers from 1 to 10^10, we need to select that maximum number i from the range such that A*b(i)+C*i does not exceed m. A and C will be given and b(i) means number of bits in the number.

Examples:

Input : 16 10 150
Output : 8

Explanation:
If we take 7 then 16*3+10*7=118,which is less than 150.
If we take 8 then 16*4+10*8=144,which is less than 144.
If we take 9 then 16*4+10*9=108,which is exceeds  154.
So answer will be 8.

Brute Force:
Traversing i from 1 to till one gets A*b(i)+C*i larger than m and then break.
Time Complexity is O(n), but n=10^10, so it will give time limit exceeded.

Optimised Approach:
Using Binary search with few modifications. We know that we need to search elements in give range which sorted, so binary search will be efficient.
Time Complexity O(logn).

First we will set lower bound to 0 and upper bound to 10¹⁰+1. Then comparing the mid element with the value of computed equation as (a*((int)log2(mid)+1)+c*mid), where number of bits is calculated by (int)log2(mid)+1 and updating lower bound accordingly. Finally when loop finishes we have the answer in lowerbound (l).

Implementation:

C++

#include <bits/stdc++.h>
using namespace std;
#define int long long int
int binsearch(int a, int c, int x)
{
    int l = 0; // Setting lower bound
    int h = 10000000000 + 1; // Setting Upper Bound
    int mid; // For mid
    while (abs(l - h)
           > 1) // Loops untill l becomes equal to h
    {
        mid = (l + h) / 2; // Calculating middle element
        int k = a * ((int)log2(mid) + 1) + c * mid;
        if (k <= x) {
            l = mid; // lower bound up
        }
        else if (k > x) {
            h = mid; // Shifting upper bound down
        }
    }
    return l;
}

int32_t main()
{
    // Driver Code

    cout << binsearch(16, 10, 150);
}

Python3

import math

def binsearch(a, c, x):
    l = 0  # Setting lower bound
    h = 10000000000+1  # Setting Upper Bound
    while abs(l-h) > 1:
        mid = (l+h)//2
        k = a*(int(math.log2(mid)+1))+c*mid  # Calculating middle element
        if(k <= x):
            l = mid  # lower bound up
        elif k > x:
            h = mid  # Shifting upper bound down
    return l

try:

    print(binsearch(16, 10, 150))
except:
    pass

Output:

Time Complexity: (logn)
Space Complexity: O(1)