# HackerRank ‘Identify Smith Numbers’ Solution

H
##### Short Problem Definition:

A Smith number is a composite number, the sum of whose digits is the sum of the digits of its prime factors obtained as a result of prime factorization (excluding 1). The first few such numbers are 4, 22, 27, 58, 85, 94, and 121.

Identify Smith Numbers

##### Complexity:

time complexity is O(sqrt(N))

space complexity is O(sqrt(N))

##### Execution:

There are many ways how to compute the prime composition of a number. I selected one with two optimization steps, there are many more. If there were many numbers to check I would use the Sieve of Eratosthenes to pre-compute the primes. The rest of the solution is straight forward. Do not forget that prime factors can also contain multiple digits.

##### Solution:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 `#!/usr/bin/py` `def` `factors(n):` `    ``f, fs ``=` `3``, []` `    ``while` `n ``%` `2` `=``=` `0``:` `        ``fs.append(``2``)` `        ``n ``/``=` `2` `    ``while` `f ``*` `f <``=` `n:` `        ``while` `n ``%` `f ``=``=` `0``:` `            ``fs.append(f)` `            ``n ``/``=` `f` `        ``f ``+``=` `2` `    ``if` `n > ``1``: fs.append(n)` `    ``return` `fs`   `def` `getIntLetterCount(n):` `    ``return` `sum``([``int``(l) ``for` `l ``in` `list``(``str``(n))])`   `def` `isSmithNumber(n):` `    ``return` `sum``([getIntLetterCount(f) ``for` `f ``in` `factors(n)]) ``=``=` `getIntLetterCount(n)`   `if` `__name__ ``=``=` `'__main__'``:` `    ``n ``=` `input``()`   `    ``if` `isSmithNumber(n):` `        ``print` `1` `    ``else``:` `        ``print` `0` 