HackerEarth Lucky Numbers problem solution

In this HackerEarth Lucky Numbers problem solution, Golu wants to find out the sum of Lucky numbers. Lucky numbers are those numbers that contain exactly two set bits. This task is very difficult for him. So Help Golu to find some of those numbers which exactly contain two set bits up to a given number N. 3 5 10 are lucky numbers where 7 14 are not.

HackerEarth Lucky Numbers problem solution.

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define f_in(st) freopen(st,"r",stdin);
#define f_out(st) freopen(st,"w",stdout);
#define M 1000000007
int main()
{
    LL t,n,d,i,j;
    cin>>t;
    assert(t>=1 && t<=100);
    while(t--)
    {
        cin>>n;
        assert(n>=1 && n<=1000000000000000000);
        if(n<=2)
        {
            cout<<"0"<<endl;
        }
        else
        {
            LL sum=0,m,k,count;
            d=3;i=1;count=0;
            while(d<=n)
            {
                sum=(sum+d)%M;
                m=1;k=1;
                //cout<<d<<" ";
                for(j=1;j<i;j++)
                {
                    //cout<<"yo"<<d+m<<" ";
                    if((d+m)<=n)
                    {
                        sum=(sum+d+m)%M;
                    }
                    else
                    {
                        break;
                    }
                    k=k*2;
                    m=m+k;
                    count++;
                }
                d=(d-1)*2+1;
                i++;
                count++;
            }
            cout<<sum<<endl;
            //cout<<count<<endl;
        }
    }
    return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> ii;
const int mod=1000000007;
const int DX[]={1,0,-1,0},DY[]={0,1,0,-1};

#define SSTR( x ) dynamic_cast< ostringstream & >( 
                ( ostringstream() << dec << x ) ).str()
#define fill(a,b) memset(a,b,sizeof(a))
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define f first
#define s second
#define Pi 3.1415926535897
#define checkbit(n,b) ( (n >> b) & 1)
#define bsearch(arr,ind) (int)(lower_bound(all(arr),ind)-arr.begin())
#define LL long long int
#define eps 1e-9
#define all(x) (x).begin(),(x).end()
LL C(int n,int k){long long ans=1;k=k>n-k?n-k:k;int j=1;for(;j<=k;j++,n--){if(n%j==0){ans*=n/j;}else if(ans%j==0){ans=ans/j*n;}else{ ans=(ans*n)/j;}} return ans;}
LL powmod(LL a,LL b) {LL res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
LL gcd(LL a,LL b){if(a==0)return(b);else return(gcd(b%a,a));}
LL powmod(LL a,LL b,LL m) {LL res=1;a%=m;for(;b;b>>=1){if(b&1)res=res*a%m;a=a*a%m;}return res;}
LL maxi = 1000000000000000000;
int main()
{
    int t;
    scanf("%d",&t);;
    assert(t and t<=10e5);
    while(t--){
        LL n;
        scanf("%lld",&n);
        assert(n and n<=maxi);
        LL ans=0;
        LL cur=2;
        bool flag=true;
        int times=1;
        while(flag){
            int div=times;
            while(flag and div){
                LL t=cur+(cur>>div);
                if(t<=n){
                    ans+=t;
                    ans%=mod;
                }
                else{
                    flag=false;
                    break;
                }
                div--;
            }
            cur=cur<<1;
            times++;
        }
        printf("%lldn",ans);
    }
    return 0;
}

HackerEarth Lucky Numbers problem solution.

Second solution

Leave a Reply