# Counting numbers whose digits all go up or down

I have created a program which takes a value x and uses this value to create a power of ten value like so 10 ** x.

This has then been used as the maximum number of a range 1..(10 ** x), which has been expanded using the splat * method to create an array of numbers, and then assigned to the variable num_array.

Using the values in this array, I want to find the total number of increasing and decreasing integers within this range. These are integers containing digits that either ascend or descend with each proceeding digit.

For example, if

x = 3


then

num_array = [*1..(10**3)] #=> num_array = [1, 2, 3, 4, .. 998, 999, 1000]


Then numbers like 234 which is ascending and 987 which is descending should be counted. Numbers like 555 fall into both categories so also should be counted but numbers like 482 should not because it doesn't follow either rule. The each method is used to evaluate which integers follow this rule in the range.

My problem is as the powers of ten increase with each method call at the end of the program, it gets slower and slower to return the end result until it calls total_nums(6) which then takes too long.

• Is there a general rule of thumb to help process really large arrays like this so it's much faster for your program to return the end result?
• What would you say are your preferred methods for such an approach like this?
• And would something like Memoization work here?
def total_nums(x)
return 0 if x == nil
return 1 if x == 0

num = 10 ** x
num_array = [*1..num]
total = 0

num_array.each do |i|
if i == i.to_s.split("").sort.join.to_i || i == i.to_s.split("").sort.reverse.join.to_i
total +=1
end
end

end

total_nums(0) #=> 1
total_nums(1) #=> 10
total_nums(2) #=> 100
total_nums(3) #=> 475
total_nums(4) #=> 1675
total_nums(5) #=> 4954
total_nums(6) #=> 12952

• You code also counts 100 or 3100 even though their digits don't "ascend or descend with each proceeding digit". Is that correct? Mar 18, 2016 at 20:20
• Yes, that is correct, if the proceeding digit is the same like 555 it is considered to belong to both the ascending and descending category even though the digit is repeated. As long as the proceeding digits don't ascend then descend (or vice versa) through the integer than the case is considered true for that integer. Mar 20, 2016 at 17:15

To make Ruby internally use a loop instead of an Array you may want to use 1.upto(10 ** x) that is an Enumerator.

But I doubt the "HUGE array" is the performance issue here.

1. First of all Ruby says to do total = .count{ ... } instead of total = 0; .each{ total += 1 if ... }
2. Then do this thing only once and store in a variable t = i.to_s.split("").sort -- x2 faster
3. Then use .chars instead of .split("") -- x4 faster

Then conversions between Integer and String seem to be unnecessary:

def total_nums x
return 0 if x == nil
return 1 if x == 0

1.upto(10 ** x).count do |i|
s = i.to_s.chars
t = s.sort
s == t || s == t.reverse
end
end


Note: probably you want either return 0 if x == 0 or start the loop from 0, not 1.

• Many Thanks Nakilon! This is extremely helpful, and hopefully will be of help to anyone with a similar problem using Ruby. This will hopefully set another mental benchmark for myself when continuing to write code in Ruby in the future in order to make it more efficient :-) Mar 20, 2016 at 17:20
• If anyone has any suggestions as to faster methods please still feel free to comment. Mar 20, 2016 at 18:01

I found quite a concise answer online that seems to be faster than the above.

def total_nums(x)
xf, nf, tf = (1..x).inject(1,:*), (1..9).inject(1,:*), (1..x+9).inject(1,:*)
(x+10)*tf/xf/nf/10 + tf/xf/nf - 10*x - 1
end


When doing a Benchmark comparison test, it certainly shows the difference in processing speed for these two results. If I tried a greater method call than total_nums(6) for the 1st method it would take too long. Here's the result for those interested.

require 'benchmark'

def total_nums x
return 0 if x == nil
return 1 if x == 0

1.upto(10 ** x).count do |i|
s = i.to_s.chars
t = s.sort
s == t || s == t.reverse
end
end

def total_nums2(x)
xf, nf, tf = (1..x).inject(1, :*), (1..9).inject(1, :*), (1..(x + 9)).inject(1, :*)
( ((x + 10) * tf) /xf/nf/10) + (tf/xf/nf) - (10 * x) - 1
end

Benchmark.bm do |x|
x.report { puts total_nums(6) }

#=>  user     system      total        real
#=> 12952
#=>  2.720000   0.010000   2.730000 (  2.760713)

x.report { puts total_nums2(6) }

#=>  user     system      total        real
#=> 12952
#=>  0.000000   0.000000   0.000000 (  0.000049)
end

• Asking for explanation of code is off-topic both as a question and as an answer. Maybe pin-point the most obscure part and ask on StackOverflow. Mar 20, 2016 at 20:35
• I've edited just to leave my findings and alternative answer. Is that acceptable? Mar 21, 2016 at 2:31
• Please reference your sources, if possible. Mar 21, 2016 at 4:03
• This was a solution I found from a codewars kata, which I thought was appropriate to mention here for further discussion. I would link to it but it'll be locked for anyone who hasn't completed it already. Mar 26, 2016 at 1:48