Lucky Numbers

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 the sum of those numbers which exactly contain two set bits upto a given number N.

3 5 10 are lucky numbers where 7 14 are not.

Example:

Input:  n = 5
Output: 8

Approach

C++

#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007
long long dp[65] = {0};
long long modularExponentiation(long long n)
{
    long long n1 = n;
    long long x = 2;
    if (dp[n1] == 0)
    {
        long long result = 1;
        while (n > 0)
        {
            if (n % 2 == 1)
                result = (result * x) % mod;
            x = (x * x) % mod;
            n = n / 2;
        }
        dp[n1] = result;
    }
    return dp[n1];
}

long long luckyNumbers(long long n)
{
    if ((n & (n - 1)) == 0)
    {
        if (n <= 2)
            return 0;
        else
        {
            long long ans = 0;
            long long c = log2(n);
            long long times = c - 1;
            for (int i = 0; i < c; i++)
            {
                long long value = modularExponentiation(i);
                value = (value * times) % mod;
                ans = ((ans % mod) + (value)) % mod;
            }
            return ans;
        }
    }
    else
    {
        long long ans = 0;
        long long c = log2(n);
        long long n1 = n - pow(2, c);
        long long c1 = log2(n1);
        long long times = c, times1 = c - 1;
        for (int i = 0; i < c; i++)
        {
            if (i <= c1)
            {
                long long value = modularExponentiation(i);
                value = (value * times) % mod;
                ans = ((ans % mod) + (value)) % mod;
            }
            else
            {
                long long value = modularExponentiation(i);
                value = (value * times1) % mod;
                ans = ((ans % mod) + (value)) % mod;
            }
        }
        times = c1 + 1;
        long long value = modularExponentiation(c);
        value = (value * times) % mod;
        ans = ((ans % mod) + (value)) % mod;
        return ans;
    }
}
int main()
{

    long long n = 5;
    cout << luckyNumbers(n) << "\n";

    return 0;
}