Happy Number

🏠 ⬅️ ➡️

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

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

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

Return true if n is a happy number, and false if not.

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
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j, k, n
    logical :: is_happy

    ! Example 1:
    n = 19
    print '(L1)', is_happy(n)

    ! Example 2:
    n = 2
    print '(L1)', is_happy(n)

contains

    function is_happy(n) result(res)
        implicit none
        integer, intent(in) :: n
        logical :: res
        integer :: digit, sum

        res = .false.
        do while (.not. res)
            sum = 0
            do while (n > 0)
                digit = mod(n, 10)
                sum = sum + digit * digit
                n = n / 10
            end do
            if (sum == 1) then
                res = .true.
            else if (any(sum == (/1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, &
                                    16777216, 67108864, 268435456, 1073741824, 4294967296, 17179869184, 68719476736, &
                                    274877906944, 1099511627776, 4398046511104, 17592186044416, 68056473382080, &
                                    271733870592640, 1061109552166400, 4304672601635200, 17014118346046928, &
                                    67772156103030912, 268553693547528384, 107374182400000000, 429496729600000000/))) then
                res = .true.
            else
                n = sum
            end if
        end do
    end function is_happy

end program main
❌ Compiled
❌ Executed
❌ Correct 
```
program happy_number
    implicit none

    integer, parameter :: INT_SIZE = selected_int_kind(13)
    integer(kind=INT_SIZE) :: n, sum, digit, i
    logical :: is_happy

    ! Read input
    read(*,*) n

    ! Initialize variables
    sum = 0
    i = 0
    is_happy = .false.

    ! Calculate the sum of the squares of the digits
    do while (i < n)
        digit = mod(n, 10)
        sum = sum + digit**2
        n = n / 10
        i = i + 1
    end do

    ! Check if the number is happy
    if (sum == 1) then
        is_happy = .true.
    else
        is_happy = .false.
    end if

    ! Print output
    if (is_happy) then
        print *, "The number is happy."
    else
        print *, "The number is not happy."
    end if

end program happy_number
```
🌐 Data from online sources 
def get_next(n):
    sum = 0
    while n > 0:
        digit = n % 10
        sum += digit * digit
        n //= 10
    return sum

def is_happy(n):
    slow, fast = n, get_next(n)
    while fast != 1 and slow != fast:
        slow = get_next(slow)
        fast = get_next(get_next(fast))
    return fast == 1

The algorithm to determine if a number is happy repeatedly performs the sum of the squares of its digits. We can use the slow and fast pointer method (also called the Floyd's cycle-finding algorithm). In this method, we have two pointers (slow and fast), both initially pointing to the input number n. In each iteration, the slow pointer moves to the next number in the sequence (by calling getNext()) while the fast pointer moves to the next of next number in the sequence. If at any point, we find that the fast pointer becomes 1, it implies that the number is a happy number. If the slow and fast pointers become equal and it is not 1, it implies that there is a cycle and the number is not a happy number.

getNext(n) function calculates the next number in the sequence by summing the squares of the digits of the current number n. This function is called in the main isHappy(n) function for updating slow and fast pointers.

🌐 Data from online sources 
int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    int slow = n, fast = getNext(n);
    while (fast != 1 && slow != fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    return fast == 1;
}

The algorithm to determine if a number is happy repeatedly performs the sum of the squares of its digits. We can use the slow and fast pointer method (also called the Floyd's cycle-finding algorithm). In this method, we have two pointers (slow and fast), both initially pointing to the input number n. In each iteration, the slow pointer moves to the next number in the sequence (by calling getNext()) while the fast pointer moves to the next of next number in the sequence. If at any point, we find that the fast pointer becomes 1, it implies that the number is a happy number. If the slow and fast pointers become equal and it is not 1, it implies that there is a cycle and the number is not a happy number.

getNext(n) function calculates the next number in the sequence by summing the squares of the digits of the current number n. This function is called in the main isHappy(n) function for updating slow and fast pointers.