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

Am I the only one who, in response to: "dont use loops" thought of the following:

   int numDigits(int num){
     if (num < 0){
       return numDigits(-1 * num);
     }
     if (num < 10){
       return 1;
     }
     if (num < 100){
       return 2;
     }
     if (num < 1000){
       return 3;
     }
     if (num < 10000){
       return 4;
     }
     if (num < 100000){
       return 5;
     }
     if (num < 1000000){
       return 6;
     }
     if (num < 10000000){
       return 7;
     }
     if (num < 100000000){
       return 8;
     }
     if (num < 1000000000){
       return 9;
     }
     return 10; // cant be more than 10 since sizeof(int) == 4, otherwise extend to 19
   }

I would prefer a solution based on multiplication than division.

If the number is less than 10, return one, otherwise is it less than 100, ...

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's more complicated.

The edge cases also seem completely clear to me in this approach, you won't accidentally write <= 100, and 0 is handled automatically.

Of course, the division and log and string methods are all fine in practice, but I'm surprised not to see this alternative mentioned.

It'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'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.

Interesting note is that the clever solution fails pretty early: 999999999999999 (15 nines) outputs 16.

I hope the author warned the students about floating point imprecision :P

I'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' simpler solutions would actually be considered correct.)

Yes, we obviously normally use a single digit to write zero, but we could logically write it as the empty string "" 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.)

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 "1.", "2.", "3.", "4.", "5.", "6.", "7.", "8.", "9.", and "10.", while zero could quite logically just be "." with no digits (as it has only leading zeroes, or we could say "nothing in the ones' place").

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.

For instance, using the "zero is written as empty string" convention, Python int() (here simplified to assume input strings of zero or more decimal digits) and str() could look like

  def int(s):
      n = 0
      for c in s:
          n *= 10
          n += "0123456789".find(c)
      return n

  def str(n):
      s = ""
      while n:
          n, d = divmod(n, 10)
          s = "0123456789"[d] + s
      return s

Seems pretty general! Yes, it'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't want to see things like "I ate tomatoes" instead of "I ate 0 tomatoes".

Never would I ever have come up with using logarithms. But I am also a math idiot. My solution used recursion.

(2019). Original submission was discussed at the time:

https://news.ycombinator.com/item?id=21500434

For base 2/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're not trying to do anything weird like signed hex - negative numbers will always be max width this way):

  hlen:
        // int hlen(uint64_t x)
        // takes an integer, returns length of hex string
        mov     x9,     #16             // max width
        clz     x0,     x0              // count binary leading zeros
        cmp     x0,     #64
        lsr     x0,     x0,     #2      // 4 bits per hex digit
        sub     x0,     x9,     x0
        cinc    x0,     x0,     eq      // if num = 0, add 1
        ret

Decimal requires looping (well, only ~20 comparisons needed for 64-bit so maybe that could be unrolled but same thing either way), so it's simpler to just use high level.

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.

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 https://stackoverflow.com/questions/68908632/is-there-a-comp...

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.

  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]//10, acc[1] + 1), initial=(n, 0)))
    return last[1]

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.

Hmm, my solution would be to convert the number to a string and return its length. Easily done in Perl:

  perl -e 'print length 987654'
  6

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.

Wouldn'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.

Looks like LLMs can shine on such a topic: https://chatgpt.com/share/e1facf96-a34f-4d07-b802-f9745a27bb...

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.

Though powers of 10 is a boundary condition so would be one of the first things I test against

In the final log10 version, can't you just solve both problems at once by adding 1 to the input?

    math.ceil(math.log10(x+1))

Was asked this one years back in a university interview. Fantastic problem

> a clever, unintuitive solution to a difficult problem

If you approach from the mathematics side of things, building on log₁₀ is the completely obvious approach to use. If it seems unintuitive, that’s just because you don’t understand logarithms.

> the autograding test cases did not include a test using a power of 10.

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, …}.)

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 interesting values. You test interesting values.

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)).

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.