# 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