-1

Recently, I came across a question posted as a challenge at a competitive site. There it was asked to find the sum of all the decimal interpretation of binary representations of numbers from 1 to n. Suppose when n = 4, so, sum will be 1 + 10 + 11 + 100 = 122. Since this number could be very large so answer should be modulo 1000000007. I came across the following solutions but was not able to optimize it.

#include<iostream>
#include<queue>
using namespace std;
int Mod(string s, int a)
{
    int res = 0, i, l = s.size();
    for( i = 0 ; i < l ; i++ )
    {
        res = ( res * 10 + s[i] - '0' ) % a;
    }
    return res;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        long long n;
        cin >> n;
        int Sum = 0, mod = 1000000007;
        queue<string> q;
        q.push("1");
        while( n > 0 )
        {
            n--;
            string s1 = q.front();
            q.pop();
            Sum = ( Sum + Mod(s1, mod) ) % mod;
            string s2 = s1;
            q.push(s1.append("0"));
            q.push(s2.append("1"));
        }
        cout << Sum << endl;
    }
    return 0;
}

Constraints: 1 <= t <= 10^5, 1 <= n <= 10^18, Allowed Time = 1 sec. Any optimization help would be admirable. Thanks in advance.

Shashank
  • 9
  • 5
  • what do you want to optimize? runtime? memory usage? readable code? – 463035818_is_not_an_ai Apr 26 '21 at 11:12
  • I forgot to mention the time limit. I have edited it. It is 1 sec. So, obviously its the runtime. – Shashank Apr 26 '21 at 11:15
  • The correct solution does not involve actually adding up anything, but is a simple mathematical formula. That "competitive site" is just a list of meaningless puzzles based on random programming or mathematical tricks. If you don't know what the trick is you won't be able to solve them. Unfortunately, those competitive sites offer no C++ or programming tutorials that teach the tricks that are needed to solve their puzzles. If someone actually wants to learn C++, the only way they'll do it is with a [C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Sam Varshavchik Apr 26 '21 at 11:15
  • `There it was asked to find the sum of all the binary representations of numbers from 1 to n.` I don't quite get the idea - there should be only one binary representation for each number on one platform. Do you mean the sum of bits used in the binary representation? – Simon Kraemer Apr 26 '21 at 11:16
  • No, @SimonKraemer, actually its the sum of all the numbers formed by binary representations of numbers from 1 to n. Suppose when n = 4, so, sum will be 1 + 10 + 11 + 100 = 122. – Shashank Apr 26 '21 at 11:21
  • 1
    @Shashank Actually, this is is the sum of the *decimal interpretation* of the binary representation of the numbers. `10` in your example is not the binary representation of two, it's the decimal representation of ten. – molbdnilo Apr 26 '21 at 11:26
  • Yes, @molbdnilo – Shashank Apr 26 '21 at 11:27
  • Are you trying to read 10^18 into an `int`? That won't work. –  Apr 26 '21 at 11:30
  • No, @jabaa. I just wrote a working code for few limits. I could change it to long long but it doesn't matter as time complexity will be still high. – Shashank Apr 26 '21 at 11:32
  • You have a brute force approach. The best idea is to close and forget the code, take a pen and paper and redesign the algorithm. You can't optimize the code. –  Apr 26 '21 at 11:34
  • Even if you could do one operation per nanosecond, your solution would literally take several decades to finish when n is 10^18. If you look at the patterns of zeros and ones, you can bring this down to a few dozen arithmetic operations rather than billions of billions (and all those memory allocations aren't helping, either). – molbdnilo Apr 26 '21 at 11:36
  • @molbdnilo removed that comment, because I misunderstood the task, though its always the same punchline: Do the maths first! – 463035818_is_not_an_ai Apr 26 '21 at 11:38
  • @largest_prime_is_463035818 I did some maths but couldn't derive sufficient conclusion from that. – Shashank Apr 26 '21 at 11:41
  • 1
    then you need to think harder ;). When `n` is eg `15` then there are `15/2` numbers that have the first bit set, `15/4` numbers that have the second bit set.... The trick is just to iterate powers of `2` instead of all numbers from `1` till `N` – 463035818_is_not_an_ai Apr 26 '21 at 11:43

1 Answers1

0

After doing some calculative math finally I have come up with the solution. Thanks, to @largest_prime_is_463035818 for providing such hints. Here is my code:

#include<iostream>
#include<cmath>
#define mod 1000000007
using namespace std;
long long power(long long x, long long y)
{
    long long res = 1LL;
    while(y)
    {
        if( y & 1LL )
        {
            res = ( res * x ) % mod;
        }
        y >>= 1LL;
        x = ( x * x ) % mod;
    }
    return res;
}
int main()
{
    long long t;
    cin >> t;
    while(t--)
    {
        long long n, i, l, m, s = 0;
        cin >> n;
        if( n && (!( n & ( n - 1LL ) )) )
        {
            l = ceil(log2(n)) + 1LL;
        }
        else
        {
            l = ceil(log2(n));
        }
        for( i = 0LL ; i < l ; i++ )
        {
        
            if( n & ( 1LL << i ) )
            {
                m = ( ( ( ( n / ( 1LL << ( i + 1LL ) ) ) * ( 1LL << i ) ) + 1LL ) + ( ( n % ( 1LL << ( i + 1LL ) ) ) % ( 1LL << i ) ) );
            }
            else
            {
                m = ( ( n / ( 1LL << ( i + 1LL ) ) ) * ( 1LL << i ) );
            }
            s = ( s + ( ( ( m % mod ) * power(10, i) ) % mod ) ) % mod;
        }
        cout << s << endl;
    }
    return 0;
}
Shashank
  • 9
  • 5