HackerEarth Let Us Understand Computer problem solution

In this HackerEarth Let Us Understand Computer problem solution Mr. ABC was recently learning about computer division. Considering the basic model of the computer suppose we wish to divide a number X by D i.e X/D and obtain the result (Note that it is integer division i.e result of 7/2 will be 3).

Now the computer will give the divide overflow error if:

The number of bits in the binary representation(without appending any leading zeroes) of the resulting number(quotient) is greater than the number of bits in the binary representation of divisor(D) (Without appending any leading zeroes).

Now Mr. ABC is given an integer X for T test cases . He wishes to find a number of such divisors D(1<=D<=X) for which divide overflow will not occur.

HackerEarth Let Us Understand Computer problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[1000005];
int main()
{
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","wb",stdout);
    
    for(ll i=1;i<=1000000;i++){
        ll r=1;
        for(ll j=1;j<=20;j++){
            r=r*2;
            if(r>i){
                break;
            }
        }
        ll z= (i*r)-1;
        a[i]=z;
    }
    ll t,x;
    cin>>t;
    while(t--)
    {
        cin>>x;
        ll id = lower_bound(a+1,a+1000000+1,x)-a;
        cout<<(x-id+1)<<endl;
    }
}

Second solution

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define irep(i,a,b) for (int i=a;i>=b;i--)
#define pii pair <int, int>
#define pll pair <ll,ll>

using namespace std;
const int ma = 1e5+5;

int bit(ll x)
{
  int ans=0;
  while(x)
  {
    x/=2;
    ans++;
  }
  return ans;
}
bool check(ll d, ll x)
{
  if(bit(x/d)<=bit(d))
    return true;
  return false;
}
ll solve(ll x)
{
  ll l =1, r = sqrt(x);
  while(l<r)
  {
    ll m = (l+r)/2;
    if(check(m,x))
      r = m;
    else
      l = m+1;
  }
  if(!check(l,x))
    return l+1;
  else
    return l;
}
int main(int argc, char* argv[])
{
  if(argc == 2 or argc == 3) 
     freopen(argv[1], "r", stdin);
  if(argc == 3) 
     freopen(argv[2], "w", stdout);
  ios::sync_with_stdio(false);
  int t;
  cin>>t;
  assert(1<=t and t<=1e6);
  rep(i,1,t)
  {
    ll x,ans=0;
    cin>>x;
    assert(1<=x and x<=1e12);
    ll tp = solve(x);
    
    cout<<x-tp+1<<endl;
  }
  
  return 0;
}

coding problems solutions