zlacker

[parent] [thread] 4 comments
1. tzs+(OP)[view] [source] 2019-11-11 01:32:57

  def digitLength(n):
      dlen = 1
      high = 9
      while n > high:
          dlen += 1
          high = 10*high + 9
      return dlen
replies(4): >>arctic+Z >>userbi+Lg >>SamRei+ou >>Mauran+L91
2. arctic+Z[view] [source] 2019-11-11 01:50:22
>>tzs+(OP)
No loops, and at least for a 64-bit type, you won't run out of stack space.

  fn digit_length_recursive(input: usize) -> usize {
      if input == 0 {
          0
      } else {
          1 + digit_length_recursive(input / 10)
      }
  }

  fn digit_length(input: usize) -> usize {
      std::cmp::max(digit_length_recursive(input), 1)
  }
3. userbi+Lg[view] [source] 2019-11-11 05:51:15
>>tzs+(OP)
When I learned computing, on the machines of the time division was very slow and multiplication was slow (early microprocessors didn't even have instructions for them), so I would certainly choose this solution over all the other ones that involve division. Modern PCs are much faster but the operations still have the same relative ranking of speeds.
4. SamRei+ou[view] [source] 2019-11-11 09:37:54
>>tzs+(OP)
One fun enhancement to this is to avoid the n^2 cost it faces with large integers.

    def digit_length(n):
        totlen = 0
        n += not n
        while n > 0:
            klen = 1
            k = 10
            while n > k * k:
                k = k * k
                klen *= 2
            n = n // k
            totlen += klen
        return totlen
5. Mauran+L91[view] [source] 2019-11-11 16:05:31
>>tzs+(OP)
That works in Python but this idea would fail in languages with fixed with integers.
[go to top]