Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I wrote this a while back when my fiance was taking a Number Theory class. I wrote about it here and it recently came back to my attention. Anytime I write a for loop in Ruby I feel kind of dirty. I would like to "Ruby-ize" this routine if there is a more Ruby way to do it. Also, is this the most efficient algorithm for this?

Original Problem:

How many numbers less than 10000 that contain the digit 5 anywhere?

(Even thought the original problem was for < 10000, I've run this much farther out)

The algorithm:

\$f(x) = 9y + \dfrac{x}{10}\$

Where \$y\$ is the previous result and \$x\$ is the power of 10 we're checking against.

i.e. \$y = 1\$ and \$x = 100\$, or \$y = 19\$ and \$x = 1000\$

or, for the more mathematically inclined

\$f(10^n)=9f(10^{n-1})+10^{n-1}\$

The code:

def numbersContaining5(pwr)
# Prints on screen the count of numbers containing a "5"
#    for each power of ten up and including the one passed in.
# pwr = the power of ten you wish to calculate to

    prev = 0
    for i in 1..pwr
        prev = (prev*9) + (10**i)/10 
        puts prev
    end
end

#call function
numbersContaining5(4) # 10^4 = 10000
share|improve this question

4 Answers 4

up vote 7 down vote accepted

I would use recurence in place of the loop - it is easier to understand the logic behind it then:

def number_containing_5(pwr)
  return 0 if pwr == 0
  number_containing_5(pwr-1) * 9 + 10**(pwr-1)
end
share|improve this answer
2  
I never even considered recursion. Nice call. Are the underscores a Ruby convention? Should I not use camel case? –  RubberDuck Jun 4 at 13:41
3  
@ckuhn203 - That's correct. There is no lower camelCase in ruby, upper CamelCase is used for constants. Some developers like dividing constants from classes, by using UPPERCASE_NOTATION for constants and CamelCase for classes and modules (this is however quite artificial, as classes are just constants). –  BroiSatse Jun 4 at 14:23
    
Thank you for the clarification. I'll read up on the style conventions. –  RubberDuck Jun 4 at 14:26
1  
I suggest changing the base case to return 0 if pwr == 0. –  200_success Jun 4 at 18:07
    
For those that prefer pure expressions to imperative returns: pwr == 0 ? 0 : number_containing_5(pwr-1) * 9 + 10**(pwr-1) (or with if/else) –  tokland Jun 4 at 19:25

Not that using recursion is wrong, but there is an abstraction for what the algorithm does, a left fold with Enumerable#reduce:

def number_containing_5(power)
  (1..power).reduce(0) { |acc, n| (9*acc) + (10**n)/10 }
end
share|improve this answer
    
I should have waited to accept! That's exactly what I was looking for. I always forget about the reduce method. –  RubberDuck Jun 4 at 19:53

So it turns out there is a better algorithm for this. The algorithm is \$10^n - 9^n\$ and you can find an explanation of it over on Mathematics Exchange. The improved algorithm completely removed my need for a loop, so I separated the test (printing) logic from the actual function and "ruby-ized" that loop instead.

def count_of_numbers_containing_5(power)
  (10**power)-(9**power)
end 

def test_it(pwr)
  (1..pwr).each {|i| puts count_of_numbers_containing_5(i)}
end

test_it 20
share|improve this answer
2  
10 ** n - 9 ** n is a good solution for Ruby, where integers are unbounded. Be careful, though, with languages where ints can overflow, where the recursive solution may be better. –  200_success Jun 4 at 18:32
    
Good call @MarnenLaibow-Koser. –  RubberDuck Jun 6 at 15:34
1  
The reason this works is straightforward: there are 10^n numbers with n or fewer digits when the digits are drawn from the 10 digits 0-9, whereas there are 9^n numbers with n or fewer digits when the digits are drawn from the 9 digits 0,1,2,3,4,6,7,8,9. The difference is therefore the number of numbers with n or fewer digits that contain one or more 5's. –  Cary Swoveland Jun 7 at 3:12

this isn't exactly using your algorithm, but I think this does the trick.

(1..10000).select { |number| number.to_s.split('').any?{ |s| s == '5' } }
share|improve this answer
1  
That is absolutely more ruby, but it's also brute force isn't it? –  RubberDuck Jun 4 at 16:25
    
Benchmark it vs your algorithm. If the difference isn't that much, then I'd argue that more clear code is a better solution. But if you need to optimize, I fully understand. But yeah benchmark it and find out. I would use github.com/evanphx/benchmark-ips rather than the stdlib benchmark as it provides a bit more information. –  Sean Jun 4 at 16:29
    
Benchmarking is kind of moot. For 10^4 (10,000) I loop 4 times. This will roughly loop (10^4)*(5!) times. Nice answer though. –  RubberDuck Jun 4 at 16:37
1  
Oh Somehow I misread the question, I thought you wanted all numbers with the 5 in it, not just how many there were. Yeah definitely use the above algorithms for that. this is if you actually want to do something with all those numbers. –  Sean Jun 4 at 18:56
    
That was my fault. I mis-worded the question a bit. –  RubberDuck Jun 4 at 18:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.