When a set should be used, we must use a set

# Problem 202. Happy Number

LeetCode Problem Link (opens new window)

Write an algorithm to determine if a number n is a happy number.

A "happy number" is defined as: for a positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1. If the number enters an infinite loop that never reaches 1, it is not a happy number.

Return True if the number is a happy number; otherwise, return False.

Example:

Input: 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)

# Solution

Although this problem seems to be a mathematical one, it is not!

The problem states that it might be an infinite loop, indicating that the sum will likely repeat during the summation process, which is critical for solving the problem!

As mentioned in Hash Table Basics (opens new window), when we need to quickly determine if an element appears in a collection, hashing should be considered.

Thus, this problem uses hashing to determine if the sum has been repeated. If it has, return false; otherwise, continue until the sum reaches 1.

To check if a sum is repeated, an unordered_set can be used.

Another challenge is the summing process. If you're not familiar with the operation on individual digits of a value, this problem can be difficult.

The C++ code is as follows:

class Solution {
public:
    // Sum of squares of digits
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            // If this sum has appeared before, it indicates an infinite loop. Immediately return false.
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

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
28

Time complexity: O(log n)
Space complexity: O(log n)

# Other Language Versions

# Java:

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Python:

(Version 1) Using a set

class Solution:
    def isHappy(self, n: int) -> bool:        
        record = set()

        while True:
            n = self.get_sum(n)
            if n == 1:
                return True
            
            # If an intermediate result appears again, it indicates a loop, and the number is not happy.
            if n in record:
                return False
            else:
                record.add(n)

    def get_sum(self, n: int) -> int: 
        new_num = 0
        while n:
            n, r = divmod(n, 10)
            new_num += r ** 2
        return new_num

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(Version 2) Using a set

class Solution:
    def isHappy(self, n: int) -> bool:
        record = set()
        while n not in record:
            record.add(n)
            new_num = 0
            n_str = str(n)
            for i in n_str:
                new_num+=int(i)**2
            if new_num==1: return True
            else: n = new_num
        return False

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

(Version 3) Using an array

class Solution:
    def isHappy(self, n: int) -> bool:
        record = []
        while n not in record:
            record.append(n)
            new_num = 0
            n_str = str(n)
            for i in n_str:
                new_num+=int(i)**2
            if new_num==1: return True
            else: n = new_num
        return False

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

(Version 4) Using fast and slow pointers

class Solution:
    def isHappy(self, n: int) -> bool:        
        slow = n
        fast = n
        while self.get_sum(fast) != 1 and self.get_sum(self.get_sum(fast)):
            slow = self.get_sum(slow)
            fast = self.get_sum(self.get_sum(fast))
            if slow == fast:
                return False
        return True
    def get_sum(self, n: int) -> int: 
        new_num = 0
        while n:
            n, r = divmod(n, 10)
            new_num += r ** 2
        return new_num

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(Version 5) Using set + concise

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = set()
        while n != 1:
            n = sum(int(i) ** 2 for i in str(n))
            if n in seen:
                return False
            seen.add(n)
        return True

1
2
3
4
5
6
7
8
9

(Version 6) Using array + concise

class Solution:
    def isHappy(self, n: int) -> bool:
        seen = []
        while n != 1:
            n = sum(int(i) ** 2 for i in str(n))
            if n in seen:
                return False
            seen.append(n)
        return True

1
2
3
4
5
6
7
8
9

# Go:

func isHappy(n int) bool {
    m := make(map[int]bool)
    for n != 1 && !m[n] {
        n, m[n] = getSum(n), true
    }
    return n == 1
}

func getSum(n int) int {
    sum := 0
    for n > 0 {
        sum += (n % 10) * (n % 10)
        n = n / 10
    }
    return sum
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# JavaScript:

var isHappy = function (n) {
    let m = new Map()

    const getSum = (num) => {
        let sum = 0
        while (n) {
            sum += (n % 10) ** 2
            n = Math.floor(n / 10)
        }
        return sum
    }

    while (true) {
        // If n has appeared, indicating an infinite loop
        if (m.has(n)) return false
        if (n === 1) return true
        m.set(n, 1)
        n = getSum(n)
    }
}

// Method 2: Using the circular linked list idea to indicate a cycle and exit the loop
var isHappy = function(n) {
    if (getN(n) == 1) return true;
    let a = getN(n), b = getN(getN(n));
    // If a === b 
    while (b !== 1 && getN(b) !== 1 && a !== b) {
        a = getN(a);
        b = getN(getN(b));
    }
    return b === 1 || getN(b) === 1 ;
};

// Method 3: Using Set() for concise code
/**
 * @param {number} n
 * @return {boolean}
 */

var getSum = function (n) {
    let sum = 0;
    while (n) {
        sum += (n % 10) ** 2;
        n =  Math.floor(n/10);
    }
    return sum;
}
var isHappy = function(n) {
    let set = new Set();   // The numbers in Set() are unique
    // If an intermediate result repeats, it indicates a loop, meaning the number is not a happy number
    while (n !== 1 && !set.has(n)) {
        set.add(n);
        n = getSum(n);
    }
    return n === 1;
};

// Method 4: Using Set(), sum using reduce
var isHappy = function(n) {
    let set = new Set();
    let totalCount;
    while(totalCount !== 1) {
        let arr = (''+(totalCount || n)).split('');
        totalCount = arr.reduce((total, num) => {
            return total + num * num
        }, 0)
        if (set.has(totalCount)) {
            return false;
        }
        set.add(totalCount);
    }
    return true;
};

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

# TypeScript:

function isHappy(n: number): boolean {
    // Utils
    // Calculate the sum of the squares of the digits of val
    function calcSum(val: number): number {
        return String(val).split("").reduce((pre, cur) => (pre + Number(cur) * Number(cur)), 0);
    }

    let storeSet: Set<number> = new Set();
    while (n !== 1 && !storeSet.has(n)) {
        storeSet.add(n);
        n = calcSum(n);
    }
    return n === 1;
};

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

# Swift:

// Sum of squares of digits of the number
func getSum(_ number: Int) -> Int {
    var sum = 0
    var num = number
    while num > 0 {
        let temp = num % 10
        sum += (temp * temp)
        num /= 10
    }
    return sum
}
func isHappy(_ n: Int) -> Bool {
    var set = Set<Int>()
    var num = n
    while true {
        let sum = self.getSum(num)
        if sum == 1 {
            return true
        }
        // If this sum has appeared before, it indicates an infinite loop
        if set.contains(sum) {
            return false
        } else {
            set.insert(sum)
        }
        num = sum
    }
}

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
28

# PHP:

class Solution {
    /**
     * @param Integer $n
     * @return Boolean
     */
    function isHappy($n) {
        // Use a set to record sums
        // End whenever a duplicate occurs
        // Return true if it equals 1, false otherwise
        $table = [];
        while ($n != 1 && !isset($table[$n])) {
            $table[$n] = 1;
            $n = self::getNextN($n);
        }
        return $n == 1;
    }

    function getNextN(int $n) {
        $res = 0;
        while ($n > 0) {
            $temp = $n % 10;
            $res += $temp * $temp;
            $n = floor($n / 10);
        }
        return $res;
    }
}

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

# Rust:

use std::collections::HashSet;
impl Solution {
    pub fn get_sum(mut n: i32) -> i32 {
        let mut sum = 0;
        while n > 0 {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        sum
    }

    pub fn is_happy(n: i32) -> bool {
        let mut n = n;
        let mut set = HashSet::new();
        loop {
            let sum = Self::get_sum(n);
            if sum == 1 {
                return true;
            }
            if set.contains(&sum) {
                return false;
            } else { set.insert(sum); }
            n = sum;
        }
    }
}

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

# C:

int get_sum(int n) {
    int sum = 0;
    div_t n_div = { .quot = n };
    while (n_div.quot != 0) {
        n_div = div(n_div.quot, 10);
        sum += n_div.rem * n_div.rem;
    }
    return sum;
}

// (Version 1) Using an array
bool isHappy(int n) {
    // sum = a1^2 + a2^2 + ... ak^2
    // first round:
    // 1 <= k <= 10
    // 1 <= sum <= 1 + 81 * 9 = 730
    // second round:
    // 1 <= k <= 3
    // 1 <= sum <= 36 + 81 * 2 = 198
    // third round:
    // 1 <= sum <= 81 * 2 = 162
    // fourth round:
    // 1 <= sum <= 81 * 2 = 162

    uint8_t visited[163] = { 0 };
    int sum = get_sum(get_sum(n));
    int next_n = sum;

    while (next_n != 1) {
        sum = get_sum(next_n);

        if (visited[sum]) return false;

        visited[sum] = 1;
        next_n = sum;
    };

    return true;
}

// (Version 2) Using fast and slow pointers
bool isHappy(int n) {
    int slow = n;
    int fast = n;

    do {
        slow = get_sum(slow);
        fast = get_sum(get_sum(fast));
    } while (slow != fast);

    return (fast == 1);
}

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

# Scala:

object Solution {
  // Introduce mutable
  import scala.collection.mutable
  def isHappy(n: Int): Boolean = {
    // Store the result after each calculation
    val set: mutable.HashSet[Int] = new mutable.HashSet[Int]()
    var tmp = n // Since parameters are immutable, a temporary variable is needed
    // Start the loop
    while (true) {
      val sum = getSum(tmp) // Get the sum of the squares of the digits of this number
      if (sum == 1) return true // If it finally equals 1, return true
      // If the set already contains this value, it indicates a loop; can return false, otherwise add this value to the set
      if (set.contains(sum)) return false
      else set.add(sum)
      tmp = sum
    }
    // A return value is needed ultimately, just return false
    false
  }

  def getSum(n: Int): Int = {
    var sum = 0
    var tmp = n
    while (tmp != 0) {
      sum += (tmp % 10) * (tmp % 10)
      tmp = tmp / 10
    }
    sum
  }
}

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
28
29
30

# C#:

public class Solution {
    private int getSum(int n) {
        int sum = 0;
        // Conversion for each digit
        while (n > 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    public bool IsHappy(int n) {
        HashSet<int> set = new HashSet<int>();
        while(n != 1 && !set.Contains(n)) { // To avoid loops
            set.Add(n);
            n = getSum(n);
        }
        return n == 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Ruby：

# @param {Integer} n
# @return {Boolean}
def is_happy(n)
    @occurred_nums = Set.new

    while true
        n = next_value(n)

        return true if n == 1

        return false if @occurred_nums.include?(n)
            
        @occurred_nums << n
    end
end

def next_value(n)
    n.to_s.chars.sum { |char| char.to_i ** 2 }
end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

← 3. Intersection of Two Arrays 5. Two Sum →