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.

Link

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

About the author

Add comment

Archives

Categories