TE
TechEcho
Home24h TopNewestBestAskShowJobs
GitHubTwitter
Home

TechEcho

A tech news platform built with Next.js, providing global tech news and discussions.

GitHubTwitter

Home

HomeNewestBestAskShowJobs

Resources

HackerNews APIOriginal HackerNewsNext.js

© 2025 TechEcho. All rights reserved.

My favorite programming problem to teach: Digit length (2019)

31 pointsby equilibrium12 months ago

19 comments

chacham1512 months ago
Am I the only one who, in response to: &quot;dont use loops&quot; thought of the following:<p><pre><code> int numDigits(int num){ if (num &lt; 0){ return numDigits(-1 * num); } if (num &lt; 10){ return 1; } if (num &lt; 100){ return 2; } if (num &lt; 1000){ return 3; } if (num &lt; 10000){ return 4; } if (num &lt; 100000){ return 5; } if (num &lt; 1000000){ return 6; } if (num &lt; 10000000){ return 7; } if (num &lt; 100000000){ return 8; } if (num &lt; 1000000000){ return 9; } return 10; &#x2F;&#x2F; cant be more than 10 since sizeof(int) == 4, otherwise extend to 19 }</code></pre>
评论 #40594864 未加载
评论 #40594369 未加载
评论 #40594147 未加载
dmurray12 months ago
I would prefer a solution based on multiplication than division.<p>If the number is less than 10, return one, otherwise is it less than 100, ...<p>You should prefer the simplest tool that can do the job. Multiplication is simpler than division. You could digress about floating point errors (Python has infinite-precision integers, but not infinite- precision floats) or performance (division may be in some contexts meaningfully slower) but those are just digressions, the important thing is that it&#x27;s more complicated.<p>The edge cases also seem completely clear to me in this approach, you won&#x27;t accidentally write &lt;= 100, and 0 is handled automatically.<p>Of course, the division and log and string methods are all fine in practice, but I&#x27;m surprised not to see this alternative mentioned.
评论 #40594197 未加载
Strilanc12 months ago
It&#x27;s very strange to me that the teacher would push the students from the correct solution using a loop, towards an incorrect solution using a logarithm. A logarithm could work in a language like C where ints can&#x27;t get too large, but Python has arbitrary precision integers so any solution using floating point numbers is doomed. For example, the code given in the post returns 16 instead of 15 for 999_999_999_999_999.
评论 #40594931 未加载
评论 #40595104 未加载
quirino12 months ago
Interesting note is that the clever solution fails pretty early: 999999999999999 (15 nines) outputs 16.<p>I hope the author warned the students about floating point imprecision :P
schoen12 months ago
I&#x27;m belatedly warming up to the idea that the digit length of the number zero is actually zero in various senses. (A footnote in the article points out that we could define it this way and then some students&#x27; simpler solutions would actually be considered correct.)<p>Yes, we obviously normally use a single digit to write zero, but we could logically write it as the empty string &quot;&quot; if we had a way to indicate that a specific number was meant. (Relative to that, writing 0 is just as unnecessary as writing 00 or 000, because we can have a rule that all leading zeroes need not be written.)<p>As another example of this intuition, suppose that we wrote all integers with a trailing decimal point. In that case the numbers from 1 to 10 would be &quot;1.&quot;, &quot;2.&quot;, &quot;3.&quot;, &quot;4.&quot;, &quot;5.&quot;, &quot;6.&quot;, &quot;7.&quot;, &quot;8.&quot;, &quot;9.&quot;, and &quot;10.&quot;, while zero could quite logically just be &quot;.&quot; with no digits (as it has only leading zeroes, or we could say &quot;nothing in the ones&#x27; place&quot;).<p>Quite a lot of arithmetic algorithms would probably work just fine with these conventions! In fact, they might have fewer exceptions or special cases than they do when they expect an explicit 0.<p>For instance, using the &quot;zero is written as empty string&quot; convention, Python int() (here simplified to assume input strings of zero or more decimal digits) and str() could look like<p><pre><code> def int(s): n = 0 for c in s: n *= 10 n += &quot;0123456789&quot;.find(c) return n def str(n): s = &quot;&quot; while n: n, d = divmod(n, 10) s = &quot;0123456789&quot;[d] + s return s </code></pre> Seems pretty general! Yes, it&#x27;s annoying or confusing if the output is going to be viewed by a human user in a larger string context without delimiters, as we probably don&#x27;t want to see things like &quot;I ate tomatoes&quot; instead of &quot;I ate 0 tomatoes&quot;.
评论 #40595653 未加载
vsnf12 months ago
Never would I ever have come up with using logarithms. But I am also a math idiot. My solution used recursion.
js212 months ago
(2019). Original submission was discussed at the time:<p><a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=21500434">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=21500434</a>
评论 #40594082 未加载
t-312 months ago
For base 2&#x2F;16 this is pretty easy if you use assembly, because most ISAs have instructions to count the leading zeros, so for eg. aarch64 to get length of hex integer (assuming you&#x27;re not trying to do anything weird like signed hex - negative numbers will always be max width this way):<p><pre><code> hlen: &#x2F;&#x2F; int hlen(uint64_t x) &#x2F;&#x2F; takes an integer, returns length of hex string mov x9, #16 &#x2F;&#x2F; max width clz x0, x0 &#x2F;&#x2F; count binary leading zeros cmp x0, #64 lsr x0, x0, #2 &#x2F;&#x2F; 4 bits per hex digit sub x0, x9, x0 cinc x0, x0, eq &#x2F;&#x2F; if num = 0, add 1 ret </code></pre> Decimal requires looping (well, only ~20 comparisons needed for 64-bit so maybe that could be unrolled but same thing either way), so it&#x27;s simpler to just use high level.
igammarays12 months ago
This is a mathy solution to a CS problem. I would’ve preferred the route to a more CS-ey solution using bit shifts and recursion. Teaches an understanding of low level representations.
nicoty12 months ago
I asked a similar question to stack overflow some time ago (to calculate the number of digits in a range) and received a performant solution using only integer arithmetic <a href="https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;68908632&#x2F;is-there-a-computationally-optimal-way-to-determine-the-number-of-digits-in-a-ra" rel="nofollow">https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;68908632&#x2F;is-there-a-comp...</a>
benmmurphy12 months ago
i feel like using the log operator for avoiding a loop is also cheating as well because under the hood there is likely to be a loop. i would have expected the non-looping solution to use either recursion or some abuse of itertools which is really just using a loop as well.<p><pre><code> import itertools def digitLength(n): if n == 0: return 1 *_, last = itertools.takewhile(lambda acc: acc[0] != 0, itertools.accumulate(itertools.repeat(None), lambda acc, x: (acc[0]&#x2F;&#x2F;10, acc[1] + 1), initial=(n, 0))) return last[1] </code></pre> the problem is interesting in python because i think the looping solution is not optimal because it performs N divisions for an arbitrarily large integer whereas I think there should be a solution that performs O(log(N)) multiplications for an arbitrarily large integer. in other languages with fixed integers its not really an issue how many operations you do since its effectively constant.
jcynix12 months ago
Hmm, my solution would be to convert the number to a string and return its length. Easily done in Perl:<p><pre><code> perl -e &#x27;print length 987654&#x27; 6 </code></pre> Similarly easy in Lisp with either of write-to-string, prin1-to-string, and princ-to-string. I expect python to have some such built-in function too.
评论 #40594858 未加载
nicbou12 months ago
Wouldn&#x27;t len(str(num)) be adequate here? This is a quite literal translation of what the code should be doing: measuring the length of the text representation of a number. The mathematical approach seems a little convoluted, although it serves the purpose of teaching a lesson.
评论 #40594258 未加载
评论 #40593899 未加载
评论 #40594032 未加载
psychoslave12 months ago
Looks like LLMs can shine on such a topic: <a href="https:&#x2F;&#x2F;chatgpt.com&#x2F;share&#x2F;e1facf96-a34f-4d07-b802-f9745a27bb83" rel="nofollow">https:&#x2F;&#x2F;chatgpt.com&#x2F;share&#x2F;e1facf96-a34f-4d07-b802-f9745a27bb...</a>
purple-leafy12 months ago
Nice read. Can see that it’s easy to take for granted that this would be a bit challenging for a real beginner to programming or syntax.<p>Though powers of 10 is a boundary condition so would be one of the first things I test against
Robin_Message12 months ago
In the final log10 version, can&#x27;t you just solve both problems at once by adding 1 to the input?<p><pre><code> math.ceil(math.log10(x+1))</code></pre>
david_allison12 months ago
Was asked this one years back in a university interview. Fantastic problem
chrismorgan12 months ago
&gt; <i>a clever, unintuitive solution to a difficult problem</i><p>If you approach from the mathematics side of things, building on log₁₀ is the <i>completely obvious</i> approach to use. If it seems unintuitive, that’s just because you don’t understand logarithms.<p>&gt; <i>the autograding test cases did not include a test using a power of 10.</i><p>That’s a pretty glaring oversight. Boundary cases are probably the most important things to cover in such tests. I’d be wanting to test things like 0, 1, 9, 10, 11, 99, 100, 101, and so forth. (Also negative numbers, unless the problem explicitly constrained it to {0, 1, 2, …}.)<p>We often talk about edge cases in testing, but this reveals that the edges can be not just at the extremes, but also at intermediate value changes. Put another way (still fuzzy!), these are the <i>interesting</i> values. You test interesting values.<p>This would also be a good place to use property testing; instead of hard-coding a bunch of tests (or perhaps as well as), compare against a large number of generated values, comparing with a known-good implementation, probably just len(str(number)).
评论 #40593981 未加载
评论 #40596196 未加载
评论 #40593953 未加载
abpavel12 months ago
This is a fantastic example of how seemingly simple programming tasks can teach deep concepts. His methodical approach to uncovering edge cases and alternative solutions demonstrates the importance of critical thinking and comprehensive testing in software development, a valuable lesson for all developers.
评论 #40600057 未加载