Woburn Challenge 1995

Problem 2: Round Numbers

A positive integer N is said to be a "round number" if the binary representation of N has as many or more zeroes than ones. For example, the integer 9, when written in binary is form, is 1001. 1001 has two zeroes and two ones: thus 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.

Input

An integer K (1 ≤ K < 2³¹)

Output

Indicate how many positive integers less than or equal to K are "round numbers" in the format shown below.

Sample Input

10

Sample Output

There are 5 round numbers less than or equal to 10.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: Sep 29, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

K ≤ 2,147,483,647 now.
Use dynamic programming!

Result of the compile:
:40:2: warning: no newline at end of file
: In function 'int main()':
:16: error: 'itoa' was not declared in this scope

Compile Failed.

My program compiles and works at home on Visual C++ Express Edition...

count is a reserved word. Try changing count to something like count2 and see if it works.

Result of the compile:
: In function 'int main()':
:21: error: 'itoa' was not declared in this scope

Compile Failed 

It still fails...

itoa isn't standard, and thus doesn't exist in g++. Sorry :(

NNNNNNNNNNNNNOOOOOOOOOOOOOOOOOOOOOOOOO~!!!!!!!!!!!!!!!!!!!!!!

Thanks Though! :(

You may consider using sscanf and sprintf as alternatives, or the istringstream and ostringstream classes in the <sstream> header.

Why? Is that gonna make itoa() work??

No, but see [url=http://cplusplus.com/reference/clibrary/cstdlib/itoa.html]this link[/url] for instructions on how to use sprintf instead of itoa.

I don't get that. What do I do with sprintf? How does it work? What do I use if I want to output the binary digits in a char array like I have done in my original solution that doesn't work on judge?

If you don't wanna use sprintf (which is a bit complicated but does stuff for you), you just gotta code your own version of itoa. It's not too hard, just a loop.

strtol/strtoul?