the_lucky_7s.rb

# Let f(N) be the number of 8s that occur when you write out all the numbers from 1 to N.
# For example:
# f(6) = 0
# f(8) = 1
# f(20) = 2
# f(80) = 9
# f(100) = 20

def f(N)
  base = []
  numbers = []

  i = 0
  loopable = N

  while loopable > 0
    digit = loopable % 10

    if i > 0
      base << base[-1] * 10 + 10**(i-1)
    else
      base << 0
    end
    
    numbers << base[i] * digit
      
    if digit == 8 
      numbers << (N % 10**i) + 1
    elsif digit > 8
      numbers << 10**i
    end

    loopable /= 10
    i += 1    
  end

  numbers.sum
end

# analysis:
#   time complexity - O(n), n = the length of digits in N
#   space complexity - O(n), n = the length of digits in N