Programming problem from competition
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
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
Replies
-
simplycoderA 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.
You are reading an archived discussion.
Related Posts
Hi friends , can some of you please list some project topics based on Cryptography ; not too tough but on the easier side ? I am a final year...
Wishing many happy returns of the day to CEan SilverScropion! 😁 May your dreams come true!
🎉🎉🎉
Very happy Birthday to CEan Silenthorde! 😁
May your dreams come true 😁
🎉🎉🎉
what is a bipolar device?
i know that conduction is due to two types of charges but how both + & - can be responsible..i feel that there is some...
Is there an ethical difference between browsing through someone’s computer files and browsing through someone's desk drawer?