contain_7s

main.rb

# case
# 0, 1, 2, 3, 4, 6, 7, 8, 9
# 10 ............., 17, 18, 19
# 20, ............, 27, 28, 29
# 10 -> 1
# 20 -> 2
# 30 -> 3
# .....
# 70 -> 8
# 80 -> 10 (70~79) + 7 = 17
# 90 -> 10 (70~79) + 8 = 18
# 100 -> 10 (70~79) + 9 = 19
# 200 -> 19 * 2 = 38
# ......
# 700 -> 19 * 7 = 133
# 800 -> 19 * 7 + 100 = 233

# some pattern
# if x < 7 => x * (digit / 10)
# 856 => (800) + (50) + (6)
# if x < 7 => return (digit-1) * x
# if x > 7 => return (digit-1) * (x-1) + 10 ^ (digit-1)
# if x = 7 => return (digit-1) * x + remain number + 1

# 10, 100, 1000, ...... n
# 10 => 1
# 100 => 9 * 1 + 10 = 19
# 1000 => 9 * 19 + 100 = 271
# 10000 => 9 * 190 + 1000 = 1900

$digit_counts = [0]
# init count for every digit
def init
  limit = 1e9
  idx = 10
  while idx <= limit
    $digit_counts << ($digit_counts.last) * 9 + idx / 10
    idx *= 10
  end
end
init

def contain_7s(n)

  return 0 if n < 7
  return 1 if n < 10

  t = n
  digit = 0
  while t >= 10
    t /= 10
    digit += 1
  end

  remaining = n - t * 10 ** digit
  pp "t: #{t}, digit: #{digit}, remaining: #{remaining}"
  if t < 7
    # ex. 356 => [0, 300) + [300, 356] => 3 * digit_counts[2] + contain_7s(56)
    $digit_counts[digit] * t + contain_7s(remaining)
  elsif t > 7
    # ex. 875 => [0 ~ 700] + (700, 799) + (800, 875) => 7 * digit_counts[2] + 100 [700~799] + count(75)
    $digit_counts[digit] * (t - 1) + 10 ** digit + contain_7s(remaining)
  else
    # ex. 7356 => [0, 7000) + (7000, 7356) => 7 * digit_counts[3] + 356
    $digit_counts[digit] * t + remaining + 1
  end
end

# use for test
def brute_force_contain_7s(n)
  (1..n).reduce(0) { |count, i|
    if i.to_s.include?('7')
      count += 1
    end
    count
  }
end

main_spec.rb

require 'rspec'
require_relative 'main'

describe 'main' do
  it '70 should return 8' do
    contain_7s(70).should == 8
  end

  it '72 should return 10' do
    contain_7s(72).should == 10
  end

  it '100 should return 19' do
    contain_7s(100).should == 19
  end

  it '1000 should return 271' do
    contain_7s(1000).should == 271
  end

  it 'start with 7' do
    contain_7s(752).should == brute_force_contain_7s(752)
  end

  it 'start with 6' do
    contain_7s(689).should == brute_force_contain_7s(689)
  end

  it 'start with 8' do
    contain_7s(89).should == brute_force_contain_7s(89)
  end

  it 'start with 9' do
    contain_7s(999).should == brute_force_contain_7s(999)
  end
end