Efficient method to check if number is binary

Question

For a programming contest question, I've come up with this solution:

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

inline bool isBasedTwo(int n) {
    while (n) {
        if ((n % 10) > 1)
            return false;
        n /= 10;
    }
    return true;
}

int main() {
    int n, count(0);
    cin >> n;
    for (int i(1); i <= n; i++)
        if (isBasedTwo(i))
            ++count;
    cout << count;
    return 0;
}

The input consists of an integer 'n'. The program must count the numbers in range of 1 to n which which only consist of zeros and ones (are a binary representation).

For example for the input '10' the program must output 2 since 1 and 10 are the only numbers in the range which only consist of zero and one digits.

But this code gets "Time Limit Exceeded" error for a few test cases. My question is, is there any better approach to this problem?

You mean a binary in decimal representation like 100rd thousand 1000 and 11? — user0042, Aug 19 '17 at 11:38
By "binary" it seems you mean a *decimal* number with only ones and zeros in it? — Some programmer dude, Aug 19 '17 at 11:38
Can you share the question link else Be more descriptive about the problem statement. — Ishpreet, Aug 19 '17 at 11:57
A regex match is a bit overkill.. You can use the expression `str.find_first_not_of("01") != std::string::npos` — Michaël Roy, Aug 19 '17 at 12:02
@ChristianHackl TLE stands for 'Time Limit Exceeded'. For detailed explanation visit [link](https://discuss.codechef.com/questions/7585/why-do-i-get-a-time-limit-exceeded?page=1#7586) — Ishpreet, Aug 19 '17 at 12:20
Some comments and at least one answer assume that the input is in text form. Your code only shows a parameter of type int. I don't see anything indicating that. Can you clarify? — Yunnosch, Aug 19 '17 at 12:30
@SamuelRobert Wouldn't constructing a string and checking that cost even more time?! — Farahmand, Aug 19 '17 at 12:32
@Farahmand Unrelated: Don't use [`#include `](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) please. — user0042, Aug 19 '17 at 13:10
@user0042 I know it would increase the compile time of the program but it doesn't matter in a programming contest. — Farahmand, Aug 19 '17 at 13:25
You can do this without looping over all the numbers, taking into account how many numbers there are in binary with a given number of digits. (Use the maths, Luke.) — molbdnilo, Aug 19 '17 at 13:40

score 0 · Answer 1 · answered Aug 19 '17 at 12:24

may be using scanf("%d ",&n) to input n helps you solve the problem because scanf() is faster than cin in order to be able to use it you must include studio or cstudio library

another thing that may work is that you try getchar() method to get the digits of n as characters and you check if each character equals 1 or 0 otherwise the number is not binary

hope this help

score 0 · Accepted Answer · answered Aug 19 '17 at 13:41

You don't need to count up to n. All you have to do, is find the largest number with ones and zeros, that when interpreted as decimal, is smaller than n.

To do this, just read the input as string, iterate over the digits, and from the first place you see a digit larger than one, change the rest to '1'.

Then interpret the string as a binary number. Which is basically the number of numbers with only ones and zeros, that are smaller than it.

#include <iostream>
#include <string>

using namespace std;

int main() {
    string n; cin >> n;
    for(int i = 0 ; i < n.size() ; i++)
        if(n[i] > '1') {
            for(int j=i ; j<n.size() ; j++)
                n[j] = '1';

            break;
        }

    cout << stoi(n, nullptr, 2) << endl;
    return 0;
}

A bit confused about why this is correct, but it is! Thank you. — Farahmand, Aug 19 '17 at 13:53

Efficient method to check if number is binary

2 Answers2