Happy Number

Updated on 02 June, 2025
Happy Number header image

Problem Statement

Determine if a given integer n is a happy number. The concept of a happy number revolves around a specific numeric transformation: starting with any positive integer, replace the integer by the sum of the squares of its digits. This process is continuously repeated using the new number. If this repetitive sequence eventually results in the number 1, the number is termed 'happy'. However, if the process forms an endless loop where the number sequence never reaches 1, the number is not 'happy'. The function must decide and return true if n is a happy number, and false otherwise.

Examples

Example 1

Input:

n = 19

Output:

true

Explanation:

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2

Input:

n = 2

Output:

false

Constraints

  • 1 <= n <= 231 - 1

Approach and Intuition

  1. Understand the transformation: The essence of the problem lies in transforming the number by summing the squares of its digits and investigating the sequence it leads to.

  2. Detect cycles with Floyd's Cycle-Finding Algorithm:

    • To detect a loop in the sequence (which indicates the number is not happy), use a fast and slow pointer technique, similar to that used in linked list cycle detection.
    • Initiate a slow variable starting with n, and a fast variable which undergoes the transformation twice for every single transformation of slow.
    • If fast becomes 1 at any stage, the number is happy.
    • If slow equals fast at any point before this, a cycle has formed, and the number is not happy.
  3. Implement digit square sum calculation:

    • A helper function to calculate the sum of squares of digits will repeatedly be used to transform the number in each step.

Considering the examples provided:

  • For n = 19, repeatedly squaring and summing the digits leads to a sequence that ends with 1, signifying a happy number.
  • For n = 2, following the same transformation process ends in a cycle (4, 16, 37, 58, 89, 145, 42, 20, 4...) which doesn't include 1, thus, it is not a happy number.

These examples illustrate the necessity to efficiently check the sequence for cycles while ensuring each digit squared sum calculation step is optimal. The provided constraints ensure our solution must handle very large values efficiently.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    int calculateSumOfSquares(int n) {
        int result = 0;
        while (n > 0) {
            int digit = n % 10;
            n = n / 10;
            result += digit * digit;
        }
        return result;
    }

    bool isHappyNumber(int n) {
        while (n != 1 && n != 4) {
            n = calculateSumOfSquares(n);
        }
        return n == 1;
    }
};

The provided C++ code defines a class Solution that contains methods to determine if a given number is a Happy Number. A Happy Number is defined as a number which eventually reaches 1 when replaced by the sum of the square of each digit.

The class has two main functions:

  • calculateSumOfSquares(int n): Computes the sum of the squares of the digits of the given number n.

    • Initializes an accumulator result to zero.
    • Uses a loop to extract each digit of n, squares it, and adds the square to result.
    • Continues until all digits are processed.
  • isHappyNumber(int n): Determines if the number n is a Happy Number.

    • Uses a loop that continues until n becomes either 1 (making it a Happy Number) or 4 (indicating it will loop endlessly rather than reaching 1).
    • Calls calculateSumOfSquares(n) in each iteration to get the sum of the squares of the digits of n.
    • If n becomes 1, the function returns true, otherwise, if it falls into the loop-indicating pattern (reaching 4), returns false.

This approach checks for the condition of looping by checking specifically for the number 4 because, in the process of determining Happy Numbers, sinking into the cycle of numbers (which includes 4) means that the number is not happy.

Implement these functions in your code base to check if numbers are Happy Numbers effectively. This implementation ensures your function is optimal in handling operations and conditions to arrive at the right conclusion.

java
class Solution {
    public int squareDigitSum(int num) {
        int sum = 0;
        while (num > 0) {
            int digit = num % 10;
            num = num / 10;
            sum += digit * digit;
        }
        return sum;
    }

    public boolean isHappy(int number) {
        while (number != 1 && number != 4) {
            number = squareDigitSum(number);
        }
        return number == 1;
    }
}

The provided solution in Java checks whether a number is a "Happy Number." A happy number is a number that leads to 1 when replaced by the sum of the square of each digit, and this process is repeated until it either equals 1 (demonstrating it is a happy number) or loops endlessly in a cycle that does not include 1.

  • Edit the solution's methods:
    • The squareDigitSum method calculates the sum of the squares of the digits of a given number num. It continues to extract and square each digit until all digits have been processed.
    • The isHappy method uses the squareDigitSum method to continually transform the input number. If the number reaches 1, the method returns true, indicating the number is happy. If the number enters a loop and reaches 4 (a part of the well-known cycle that indicates unhappiness), it will eventually lead to 4 repeatedly, and the method returns false.

This solution effectively determines if a given integer is a happy number using a repetitive squaring and summing process, with a cycle detection that utilizes the specific nature of mathematical properties of happy numbers.

python
class Solution:

    def check_happiness(self, num: int) -> bool:

        def next_value(val: int) -> int:
            result = 0
            while val > 0:
                val, remainder = divmod(val, 10)
                result += remainder**2
            return result

        while num != 1 and num != 4:
            num = next_value(num)

        return num == 1

The provided Python solution checks if a number is a "Happy Number" using a class named Solution with a method check_happiness. Here's how the solution operates:

  1. The method check_happiness accepts an integer num and defines a nested function next_value that calculates the next number based on the sum of the squares of the digits of the current number (val).

  2. In next_value, val is decomposed digit by digit using division and modulo operations. Each digit from the decomposition is squared and added to a result variable until the entire number is processed.

  3. The method repeatedly updates the number num by calling next_value and continues this process until num either becomes 1 (indicating a happy number) or enters a loop by becoming 4 (indicating it's not a happy number).

  4. The loop detection hinges on recognizing the well-known cycle in unhappy numbers, where repeated transformations of digits eventually lead to the number 4.

  5. Finally, check_happiness returns True if the number is happy (when num equals 1) or False if it's not.

This code efficiently and elegantly determines the happiness of a number by cleverly using a helper function for computation and loop detection based on the properties of happy numbers.

Comments

No comments yet.