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 1010+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:
8
Time Complexity: (logn)
Space Complexity: O(1)
