202. Happy Number

Intuition

A happy number is defined by the process of repeatedly summing the squares of its digits until the result is 1, or it forms a cycle that does not include 1.

Approach

1. Helper Function: Define a helper function get_next(n) that computes the sum of the squares of digits of n.
2. Cycle Detection: Use a set seen to keep track of numbers encountered during the transformation process to detect cycles.
3. Transformation Loop: Continuously apply get_next to n until either n becomes 1 (indicating n is a happy number) or a cycle is detected.
4. Return Result: If n becomes 1 during the process, return True. If a cycle is detected (where n has already been seen), return False.

Complexity

Time Complexity:

O(log n). Each transformation step involves computing the sum of squares of digits, which is proportional to the number of digits in n.

Space Complexity:

O(log n) due to the space used by the seen set, which stores numbers encountered during the transformation process.

Code

C++

class Solution {
public:
    bool isHappy(int n) {
        if (n == 1 || n == 7) {
            return true;
        }
        while (n > 9) {
            int sum = 0;
            while (n > 0) {
                int digit = n % 10;
                sum += digit * digit;
                n /= 10;
            }
            n = sum;
            if (n == 1 || n == 7) {
                return true;
            }
        }
        return n == 1 || n == 7;
    }
};

Python

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

Java

class Solution {
    public boolean isHappy(int n) {
        if (n == 1 || n == 7) {
            return true;
        }
        while (n > 9) {
            int sum = 0;
            while (n > 0) {
                int digit = n % 10;
                sum += digit * digit;
                n /= 10;
            }
            n = sum;
            if (n == 1 || n == 7) {
                return true;
            }
        }
        return n == 1 || n == 7;
    }
}

JavaScript

var isHappy = function (n) {
    if (n == 1 || n == 7) {
        return true;
    }
    while (n > 9) {
        let arr = n.toString().split("").map(Number);

        let powered = arr.map((num) => {
            return Math.pow(num, 2);
        });
        n = powered.reduce(function (accumulator, currentValue) {
            return accumulator + currentValue;
        }, 0);
        if (n == 1 || n == 7) {
            return true;
        }
    }
    if (n != 1 || n != 7) {
        return false;
    }
};