Count of binary numbers from 1 to n

user_15680552 0
Viewed 221

I want to find the number of numbers between 1 and n that are valid numbers in base two (binary).

1 ≤ n ≤ 10^9

For example, suppose n is equal to 101.

Input: n = 101

In this case, the answer is 5

Output: 1, 10, 11, 100, 101 -> 5

Another example

Input: n = 13
Output: 1, 10, 11 -> 3

Here is my code...

#include <iostream>

using namespace std;

int main()
{
    int n, c = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int temp = i;
        bool flag = true;
        while(temp != 0) {
            int rem = temp % 10;
            if (rem > 1)
            {
                flag = false;
                break;
            }
            temp /= 10;
        }
        if (flag)
        {
            c++;
        }
    }
    cout << c;
    return 0;
}

But I want more speed.
(With only one loop or maybe without any loop)

Thanks in advance!

binary algorithm c++
2 Answers

The highest binary number that will fit in a d-digit number d1 d2 ... dn is b1 b2 ... bn where

bi = 0 if di = 0, and
bi = 1 otherwise.

A trivial implementation using std::to_string:

int max_binary(int input) {
    int res = 0;
    auto x = std::to_string(input);
    for (char di : x) {
        int bi = x == '0' ? 0 : 1;
        res = 2 * res + bi;
    }
    return res;
}
user_15484680

Details: In each step, if the digit was one, then we add 2 to the power of the number of digits we have. If the number was greater than 1, then all cases are possible for that number of digits, and we can also count that digit itself and change the answer altogether (-1 is because we do not want to calculate the 0).

#include <iostream>

using namespace std;

int main()
{
    long long int n, res = 0, power = 1;
    cin >> n;

    while(n != 0) {
        int rem = n % 10;
        if (rem == 1) {
            res += power;
        } else if (rem > 1) {
            res = 2 * power - 1;
        }
        n /= 10;
        power *= 2;
    }
    cout << res;
    return 0;
}
user_156805520
Related