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)