Question

Formatted question description: https://leetcode.ca/all/202.html

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:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

Algorithm

The example 19 given in the title is a happy number, so let’s look at a situation that is not a happy number. For example, the number 11 has the following calculation process:

1^2 + 1^2 = 2 2^2 = 4 4^2 = 16 1^2 + 6^2 = 37 3^2 + 7^2 = 58 5^2 + 8^2 = 89 8^2 + 9^2 = 145 1^2 + 4^2 + 5^2 = 42 4^2 + 2^2 = 20 2^2 + 0^2 = 4

At the end of the calculation, the number 4 appears again, then the following numbers will repeat the previous order. This cycle does not contain 1, then the number 11 is not a happy number. After discovering the pattern, we can consider how to use code it.

Use HashSet to record all the numbers that have appeared, and then every time a new number appears, look for it in HashSet to see if it exists,

if it does not exist, add it to the table,
if it exists, jump out of the loop, and determine whether the number is 1,
- if it is 1. Return true,
- return false if not 1

Code

    class Solution {
        public boolean isHappy(int n) {

            HashSet<Integer> set = new HashSet<Integer>();

            while (!set.contains(n)) {
                set.add(n);

                n = getSum(n);

                if (n == 1) {
                    return true;
                }
            }

            return false;
        }

        public int getSum(int current) {
            int sum = 0;

            while (current > 0) {
                sum += Math.pow(current % 10, 2);
                current /= 10;
            }

            return sum;
        }
    }

    class Solution_iteration {
        public boolean isHappy(int n) {
            HashSet<Integer> st = new HashSet<Integer>();
            while (n != 1) {
                int sum = 0;
                while (n > 0) {
                    sum += (n % 10) * (n % 10);
                    n /= 10;
                }
                n = sum;
                if (st.contains(n)) {
                    break;
                }
                st.add(n);
            }

            return n == 1;
        }
    }

    // if find 4 then unhappy
    class Solution_math {
        public boolean isHappy(int n) {
            while (n != 1 && n != 4) {
                int sum = 0;
                while (n > 0) {
                    sum += (n % 10) * (n % 10);
                    n /= 10;
                }
                n = sum;
            }
            return n == 1;

        }
    }
}


############

class Solution {
    public boolean isHappy(int n) {
        int slow = n, fast = next(n);
        while (slow != fast) {
            slow = next(slow);
            fast = next(next(fast));
        }
        return slow == 1;
    }

    private int next(int x) {
        int y = 0;
        for (; x > 0; x /= 10) {
            y += (x % 10) * (x % 10);
        }
        return y;
    }
}

// OJ: https://leetcode.com/problems/happy-number/
// Time: O(1)
// Space: O(1)
class Solution {
public:
  bool isHappy(int n) {
    unordered_set<int> s;
    while (n != 1 && !s.count(n)) {
      s.insert(n);
      int next = 0;
      while (n) {
        next += pow(n % 10, 2);
        n /= 10;
      }
      n = next;
    }
    return n == 1;
  }
};

class Solution:
    def isHappy(self, n: int) -> bool:
        def next(x):
            y = 0
            while x:
                x, v = divmod(x, 10)
                y += v * v
            return y

        slow, fast = n, next(n)
        while slow != fast:
            slow, fast = next(slow), next(next(fast))
        return slow == 1

############

class Solution(object):
  def isHappy(self, n):
    """
    :type n: int
    :rtype: bool
    """
    record = {}
    sq_sum = 0
    while n != 1:
      sq_sum = 0
      sub_num = n
      while sub_num > 0:
        sq_sum += (sub_num % 10) * (sub_num % 10)
        sub_num /= 10
      if sq_sum in record:
        return False
      else:
        record[sq_sum] = 1
      n = sq_sum
    return True

func isHappy(n int) bool {
	next := func(x int) (y int) {
		for ; x > 0; x /= 10 {
			y += (x % 10) * (x % 10)
		}
		return
	}
	slow, fast := n, next(n)
	for slow != fast {
		slow = next(slow)
		fast = next(next(fast))
	}
	return slow == 1
}

function isHappy(n: number): boolean {
    const getNext = (n: number) => {
        let res = 0;
        while (n !== 0) {
            res += (n % 10) ** 2;
            n = Math.floor(n / 10);
        }
        return res;
    };

    let slow = n;
    let fast = getNext(n);
    while (slow !== fast) {
        slow = getNext(slow);
        fast = getNext(getNext(fast));
    }
    return fast === 1;
}

impl Solution {
    pub fn is_happy(n: i32) -> bool {
        let get_next = |mut n: i32| {
            let mut res = 0;
            while n != 0 {
                res += (n % 10).pow(2);
                n /= 10;
            }
            res
        };
        let mut slow = n;
        let mut fast = get_next(n);
        while slow != fast {
            slow = get_next(slow);
            fast = get_next(get_next(fast));
        }
        slow == 1
    }
}

202 - Happy Number

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions