HackerRank Challenge - Día 4

En esta serie de posts estoy documentando mi experiencia intentando entrar entre los mil mejores programadores de HackerRank, un sitio para practicar ejercicios de programación.

Nota: Si aún no lo has hecho, te recomiendo leer el día 1 primero.

Ayer terminé en el ranking 5,894.

El ejercicio de hoy se llama Special Multiple. Lo que nos piden es encontrar el menor número X compuesto de 9’s y 0’s únicamente, tal que X sea un múltiplo de un número N.

Por ejemplo, si N es 5, la respuesta es 90, porque 90 es el menor número compuesto de 9’s y 0’s que es múltiplo de 5.

La clave de este ejercicio era entender la forma en que debíamos probar los números: 9, 90, 99, 900, etc., y darse cuenta que es la misma forma en que se incrementan los números binarios: 1, 10, 11, 100, etc.

El código que pasó la prueba es el siguiente:

def test(digits, n)
  num = "9#{'0' * (digits - 1)}".to_i
  max = ("1" * (digits - 1)).to_i(2)
  i = 0
  while i <= max
    sum = i.to_s(2).rjust(digits - 1, "0").chars.map { |k| k.to_i * 9 }.join("").to_i
    if (num + sum) % n == 0
      return num + sum
    end
    i += 1
  end
end

n = gets.chomp.to_i
found = false
digits = 1
until found
  if result = test(digits, n)
    puts result
    found = true
  end
  digits += 1
end

Todavía se puede simplificar más, pero esto fue suficiente para pasar. Mi nuevo ranking es 4,813!