NUHMAN.com

Problem Statement

A happy number is a number defined by the following process:

1. Start with any positive integer.
2. Replace the number by the sum of the squares of its digits.
3. Repeat the process until:

• The number equals 1, or
• The number loops endlessly in a cycle that does not include 1.

If a number ends up at 1, then it is a happy number. Otherwise, it is not a happy number.

Return true if the given number is a happy number, otherwise return false.

Function Signature:

go

func isHappy(n int) bool

Example 1:

go

n := 19
fmt.Println(isHappy(n)) // Output: true

Example 2:

go

n := 2
fmt.Println(isHappy(n)) // Output: false

Constraints:

• 1 <= n <= 2^31 - 1

Approach

To determine whether a number is a happy number, we need to:

1. Replace the number by the sum of the squares of its digits repeatedly.
2. Check if we reach 1 or if we fall into a cycle (i.e., the process starts repeating).

The key insight is that if the number becomes part of a cycle that doesn’t include 1, it is not a happy number.

Cycle Detection:

We can use a set or a hash map to track the numbers we have seen during the sum-of-squares process. If we encounter a number that we've seen before, it means we've entered a cycle, and the number is not a happy number.

Steps:

1. Define a function getNext(n int) int to return the sum of the squares of the digits of n.
2. Use a loop to calculate the next number until we either reach 1 or encounter a previously seen number.
3. If we encounter a previously seen number, we know we've entered a cycle, and the number is not happy.
4. Return true if we reach 1, otherwise return false.

Time Complexity:

The time complexity is O(log n) due to the digit-squaring process, where the number of digits of n is proportional to log n.

Go Implementation

go

package main

import "fmt"

// Function to calculate the sum of the squares of the digits of n
func getNext(n int) int {
    sum := 0
    for n > 0 {
        digit := n % 10
        sum += digit * digit
        n /= 10
    }
    return sum
}

// Function to determine if a number is happy
func isHappy(n int) bool {
    seen := make(map[int]bool) // Set to track numbers we've seen
    for n != 1 {
        if _, exists := seen[n]; exists {
            return false // We encountered a cycle
        }
        seen[n] = true
        n = getNext(n) // Get the next number in the sequence
    }
    return true // Reached 1, so it's a happy number
}

func main() {
    // Example 1
    n1 := 19
    fmt.Println(isHappy(n1)) // Output: true

    // Example 2
    n2 := 2
    fmt.Println(isHappy(n2)) // Output: false
}

Explanation of the Code:

1. getNext Function:

• Input: Takes an integer n.
• Process: For each digit of n, squares it and adds the result to the sum.
• Output: Returns the sum of the squares of the digits of n.

2. isHappy Function:

• Input: Takes an integer n and determines if it is a happy number.
• Set for Cycle Detection: We use a map[int]bool (set) to track the numbers that we encounter during the process.
• Loop: The loop continues until n becomes 1 or we encounter a cycle (i.e., a number we have seen before).
• Cycle Detection: If a number repeats, we return false because we've detected a cycle.
• Return Value: If n becomes 1, return true (happy number); otherwise, return false.

3. Main Function:

• Creates two test cases (n1 and n2).
• Calls isHappy and prints the result for each case.

Example Walkthrough

Example 1:

Input:

go

n := 19

• Start with n = 19:
• 1^2 + 9^2 = 1 + 81 = 82
• Next, for n = 82:
• 8^2 + 2^2 = 64 + 4 = 68
• Next, for n = 68:
• 6^2 + 8^2 = 36 + 64 = 100
• Next, for n = 100:
• 1^2 + 0^2 + 0^2 = 1 + 0 + 0 = 1
• We reached 1, so 19 is a happy number.

Output: true

Example 2:

Input:

go

n := 2

• Start with n = 2:
• 2^2 = 4
• Next, for n = 4:
• 4^2 = 16
• Next, for n = 16:
• 1^2 + 6^2 = 1 + 36 = 37
• Next, for n = 37:
• 3^2 + 7^2 = 9 + 49 = 58
• Next, for n = 58:
• 5^2 + 8^2 = 25 + 64 = 89
• Next, for n = 89:
• 8^2 + 9^2 = 64 + 81 = 145
• Next, for n = 145:
• 1^2 + 4^2 + 5^2 = 1 + 16 + 25 = 42
• Next, for n = 42:
• 4^2 + 2^2 = 16 + 4 = 20
• Next, for n = 20:
• 2^2 + 0^2 = 4 + 0 = 4
• We have entered a cycle with 4, so 2 is not a happy number.

Output: false

Conclusion

The LeetCode 202: Happy Number problem can be efficiently solved by detecting cycles using a set. By repeatedly calculating the sum of the squares of the digits and checking for repeated values, we can determine if a number is happy or not.

This solution runs in O(log n) time complexity, which is efficient enough for the input limits.