Teaching Kids Programming – Algorithms to Determine a Happy Number

Teaching Kids Programming: Videos on Data Structures and Algorithms

Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process:

1. Starting with any positive integer, replace the number by the sum of the squares of its digits.
2. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
3. Those numbers for which this process ends in 1 are happy.
4. Return true if n is a happy number, and false if not.

Example 1:
Input: n = 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

Example 2:
Input: n = 2
Output: false

Check Happy Number Algorithms

Using a set to keep tracking the numbers we have generated. Then, for each number, we extract the digits by digits, square it, and compute the sum until it either is 1 or it has appeared in the set.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def isHappy(self, n: int) -> bool:
        d = set()
        while n != 1 and (not n in d):
            d.add(n)
            cur = n
            a = 0
            while cur > 0:
                a += (cur % 10)**2
                cur //= 10
            n = a
        return n == 1

class Solution:
    def isHappy(self, n: int) -> bool:
        d = set()
        while n != 1 and (not n in d):
            d.add(n)
            cur = n
            a = 0
            while cur > 0:
                a += (cur % 10)**2
                cur //= 10
            n = a
        return n == 1

We can convert the number into the string, then iterate over the digits, convert it back to integer, square it…

1
2
3
4
5
6
7
8
9
10

class Solution:
    def isHappy(self, n: int) -> bool:
        d = set()
        while n != 1 and (not n in d):
            d.add(n)
            a = 0
            for i in str(n):
                a += int(i)**2
            n = a
        return n == 1

class Solution:
    def isHappy(self, n: int) -> bool:
        d = set()
        while n != 1 and (not n in d):
            d.add(n)
            a = 0
            for i in str(n):
                a += int(i)**2
            n = a
        return n == 1

We can use the list comprehension to make the code shorter.

1
2
3
4
5
6
7

class Solution:
    def isHappy(self, n: int) -> bool:
        d = set()
        while n != 1 and (not n in d):
            d.add(n)
            n = sum([int(x)**2 for x in str(n)])
        return n == 1

class Solution:
    def isHappy(self, n: int) -> bool:
        d = set()
        while n != 1 and (not n in d):
            d.add(n)
            n = sum([int(x)**2 for x in str(n)])
        return n == 1

See also: Happy Number Detection Algorithm using Hash Set

–EOF (The Ultimate Computing & Technology Blog) —