Programming problem from competition

Manish Goyal

Manish Goyal

@manish-r2Hoep • Oct 18, 2024
here is a problem which i face when i participate in a online programming competition
can any any one solve it
Problem Statement:

Now comes an interesting math game.
How many of the numbers 2^m (0 <= m <= M),m is integer, have leading digit 1 in the decimal notation ?


Input:

There are multiple cases, end with EOF
each case have one integer, M. (0 <= M <= 10^15 )
Output:
Each case a line, the number of the numbers which have leading digit 1.

Sample Input
2
4

Sample Output
1
2
Like 0 Replies 1

Replies

Welcome, guest

Join CrazyEngineers to reply, ask questions, and participate in conversations.

Sign up Log in

CrazyEngineers powered by Jatra Community Platform

  • simplycoder

    simplycoder

    @simplycoder-NsBEdD • Sep 23, 2012

    A simple approach would be using modular arithmetic and if the resultant is as desired then increase the counter by 1.
    We shall assume that this verification requires about N steps.

    Consider the limits of the input, the range is far too much to repeat the N steps for a computer to provide answer in given time. But then theoretically this approach works.

    Now lets switch on to a better algorithm.

    This is a classic case of benford law.
    Probability of digit d is log(1+1/d).
    So for 1, its M*log2
    since the numbers are powers of 2, the error will be very less and can be neglected.
    after coding this, floor the answer and add 1 to it as we have 2[sup]0[/sup]=1
    (or you can just ceil the answer).
    If this is not clear then I shall post the code as well.
    0