How many digits?
Imagine you took all the integers between n
and m
(exclusive, n < m
) and concatenated them together. How many digits would you have? Write a function that takes two numbers and returns how many digits. Note that the numbers can get very big, so it is not possible to build the string in the general case.
Examples:
(num-digits 0 1) ;=> 0 (there are no integers between 0 and 1)
(num-digits 0 10) ;=> 9 (1, 2, 3, 4, 5, 6, 7, 8, 9)
(num-digits 9 100) ;=> 180
UPDATE: My original example was wrong. The last one should return 180, not 179. It was my fault, due to off by one errors.
Thanks to this site for the problem idea, where it is rated Expert in Python. The problem has been modified.
Please submit your solutions as comments on this gist.
To subscribe: https://ericnormand.me/newsletter
Nice solution, @nbardiuk! It is very fast and also compact. I ran my code against your tests and got the same results as yours,
except for the large exponentiated value at the end.
My solution is too long to clutter this space, but if anyone is interested it is here. I also wrote quite a bit of documentation, and it also works with non-decimal bases.
Trying to achieve maximum speedup, and not being clever enough, I used boundary positions and classification of corner cases
together with multi-methods to prevent messy logic branching, end ended taking a crash course in hierarchies and dispatching.
This approach reminds me of a long ago business requirement document consisting of a table of 30 outcome scenarios , each with
a half-dozen conditions (columns). I had to implement in Java something similar to multi-methods, or be faced with a tangled mess
of if/else branches.
In this problem, the classification allows treating all similar ranges with a single operation, and the cost of dispatch is limited to
at most four calls per num-digits invocation. Here is a rough estimate with
O(log N)
performance:Speaking of performance, I tried to find one-op formula for
Summation( base^n X n)
over a range but couldn't find one, althoughthere is one for
base^n
. If such a thing exists thennum-digits
isO(1)
, but without it I could only doO(log N)
, N being the largestwidth from the boundaries.
Does anyone mathematically inclined know of that magic formula? Here is an implementation of sum-of-powers from this wikipedia article: