Count the number of positive integers less than N that does not contains digit 4.

positive_non_four.rb

#
# Count the number of positive integers less
# than N that does not contains digit 4.
#
# Source: http://www.careercup.com/question?id=4752301805797376

class PositiveNonFour

  def count_integers_non_four_less_than(max, strategy = :brute_force)
    @filter = 4
    case strategy
      when :brute_force
        brute_force max
      when :nine_based_numeral_system
        nine_based_numeral_system max
    end
  end

  # Just loop over all integers between 0 and given integer
  # and search for those that do not include the filter
  #
  def brute_force(max)
    count = @filter - 1
    for number in @filter..(max-1)
      unless number.to_s.include? @filter.to_s
        count += 1
      end
    end
    count
  end


  # Considering a base-9 numeral system, if we are counting numbers skipping
  # digit 4, basically 10 is the 9th number, 100 is the 81th, and so on.
  #
  #  (1) Does the input number contain digit 4? If yes, then replace the highest digit
  #      4 with 3, and change all the following digits to 9.
  #  (2) From lowest to highest digit, multiply the n-th digit by 9^(n-1).
  #  (3) Subtract the result by one since we are getting the number of integers strictly
  #      less than N.
  #  (4) If the number is great than 4 just substract one as you don't need to count all
  #      4starting subnumbers
  #
  def nine_based_numeral_system(max)
    sw  = count = 0
    pos = max.to_s.length

    max.to_s.scan(/./).each do |number|
      number = number.to_i
      if number == @filter && sw == 0
        number -= 1                     # As will be the same result 4xx than 399
        sw      = 1
      elsif sw == 1
        number = 9                      # As it has a previous 4 so this is the same as 3xxx
      elsif number > @filter
        number -= 1
      end
      pos   -= 1
      count += number * 9 ** pos
    end
    count -= 1
  end
end


class PositiveNonFourTester
  def test
    data_provider.each do |key, value|
      algorithms.each do |algorithm|
        count = counter.count_integers_non_four_less_than(key, algorithm)
        if count == value
          puts '.'
        else
          puts "Expected #{value} is not equal to #{count} for seed #{key} using #{algorithm.to_s}"
        end
      end
    end
  end

  def algorithms
    [ :brute_force, :nine_based_numeral_system ]
  end

  def data_provider
    {
        38    => 33,
        39    => 34,
        50    => 35,
        159   => 124,
        3651  => 2628,
        3399  => 2509,
        10    => 8,
        1000  => 728,
        10000 => 6560,
        20    => 17,
        100   => 80,
        200   => 161,
        40    => 35,
        41    => 35,
        42    => 35,
    }
  end

  def counter
    @__counter__ ||= PositiveNonFour.new
  end
end

PositiveNonFourTester.new.test

check your test cases
1 => 1
2 => 2
3 => 3
4 => 3
5 => 4
6 => 5
7 => 6
8 => 7
9 => 8
10 => 9
11 => 10
12 => 11
13 => 12
14 => 12
15 => 13
16 => 14
17 => 15
18 => 16
19 => 17
20 => 18
21 => 19
22 => 20
23 => 21
24 => 21
25 => 22
26 => 23
27 => 24
28 => 25
29 => 26
30 => 27