LEETCODE PRACTICE

 

UNDERSTANDING HAPPY NUMBERS

 

Introduction

         

        This presentation explores the concept of Happy Numbers, their properties, algorithms for determining their status, and practical applications in various fields.

 

What is a happy number ?

         

        a happy number is a number that eventually reaches 1 when replaced repeatedly by the sum of the squares of its digits. An unhappy number (also known as a sad number) is a number that does not reach 1 and instead enters a cycle that never reaches 1.

 

Steps to determine if a number is happy:

 

        1.Start with a number n.

        2.Replace n by the sum of the squares of its digits. 

        3.Repeat the process with the new value. 

        4.If n eventually reaches 1, then n is a happy number. 

        5.If n enters a cycle that does not include 1, then n is an unhappy number. 

Example:

Happy Number Example:

Let's take 19 as an example:

• 1^2 + 9^2 = 1 + 81 = 82

• 8^2 + 2^2 = 64 + 4 = 68

• 6^2 + 8^2 = 36 + 64 = 100

• 1^2 + 0^2 + 0^2 = 1 + 0 + 0 = 1

Since the process eventually reaches 1, 19 is a happy number.

Unhappy Number Example:

Let's take 4 as an example:

• 4^2 = 16

• 1^2 + 6^2 = 1 + 36 = 37

• 3^2 + 7^2 = 9 + 49 = 58

• 5^2 + 8^2 = 25 + 64 = 89

• 8^2 + 9^2 = 64 + 81 = 145

• 1^2 + 4^2 + 5^2 = 1 + 16 + 25 = 42

• 4^2 + 2^2 = 16 + 4 = 20

• 2^2 + 0^2 = 4 + 0 = 4

We see that the number 4 is cycling through the same numbers and will never reach 1. Thus, 4 is an unhappy number.

Approach to solve the problem

1.Use a set to detect cycles:

       As we repeatedly square the digits of the number, we can use a set to keep track of previously encountered numbers.

       If we encounter a number that we've already seen, it means we're in a cycle and the number is unhappy.

       If we reach 1, the number is happy.

2.Implementation:

    Define a helper function to compute the sum of squares of digits of a number.   

    Use a loop or recursion to repeatedly compute the sum of squares until either:

    We reach 1 (return true).

    We encounter a number we've seen before (return false).

 Java Solution (for LeetCode Problem: Happy Number): 

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        
        while (n != 1) {
            if (seen.contains(n)) {
                return false; 
            }
            seen.add(n);
            n = sumOfSquares(n); 
        }
        
        return true; 
    }
   
    private int sumOfSquares(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int number = 19;
        System.out.println(solution.isHappy(number));
    }
}

Time Complexity

     Each step reduces the number significantly, and the number of digits decreases quickly, so the time complexity is approximately O(log n) for each iteration.

       The space complexity is O(k), where k is the number of unique numbers encountered, which is bounded by the size of the cycle. 

Conclusion 

    Happy Numbers extend beyond mere mathematical puzzles; they apply to cryptography, AI, game development, and psychology, demonstrating their versatile nature.