Algorithm
Problem Name: 202. 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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
bool has_cycle(int *set, int x, int k) {
int i;
for (i = 0; i < x; i ++) {
if (set[i] == k) return true;
}
return false;
}
bool isHappy(int n) {
int i, k;
int *set, sz, x;
//assert(n > 0);
sz = 100;
x = 0;
set = malloc(sz * sizeof(int));
//assert(set);
do {
if (x == sz) {
sz *= 2;
set = realloc(set, sz * sizeof(int));
//assert(set);
}
set[x ++] = n;
k = 0;
while (n) {
i = n % 10;
n = n / 10;
k += i * i;
}
n = k;
} while (k != 1 && !has_cycle(set, x, k));
free(set);
return k == 1 ? true : false;
}
Input
n = 19
Output
true
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean isHappy(int n) {
int slow = n;
int fast = getSquareDigitSum(n);
while (fast != 1 && slow != fast) {
slow = getSquareDigitSum(slow);
fast = getSquareDigitSum(getSquareDigitSum(fast));
}
return fast == 1;
}
private int getSquareDigitSum(int n) {
int squareDigitSum = 0;
while (n > 0) {
int digit = n % 10;
squareDigitSum += digit * digit;
n /= 10;
}
return squareDigitSum;
}
}
Input
n = 19
Output
true
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const isHappy = function(n) {
const arr = [];
let tmp = n;
while (arr.indexOf(tmp) === -1) {
arr.push(tmp);
let res = ("" + tmp)
.split("")
.reduce((ac, str) => ac + Math.pow(+str, 2), 0);
if (res === 1) {
return true;
}
tmp = res;
}
return false;
};
Input
n = 2
Output
false
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
mem = set()
while n != 1:
n = sum([int(i) ** 2 for i in str(n)])
if n in mem: return False
else: mem.add(n)
else: return True
Input
n = 2
Output
false
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0202_HappyNumber
{
public bool IsHappy(int n)
{
var map = new HashSet < int>();
while (!map.Contains(n))
{
map.Add(n);
var newValue = 0;
while (n > 0)
{
var digit = n % 10;
newValue += digit * digit;
n /= 10;
}
if (newValue == 1) return true;
n = newValue;
}
return false;
}
}
}
Input
n = 19
Output
true