Dare2Solve
A happy number is defined by the process of repeatedly summing the squares of its digits until the result is 1, or it forms a cycle that does not include 1.
Helper Function: Define a helper function get_next(n)
that computes the sum of the squares of digits of n
.
Cycle Detection: Use a set seen
to keep track of numbers encountered during the transformation process to detect cycles.
Transformation Loop: Continuously apply get_next
to n
until either n
becomes 1 (indicating n
is a happy number) or a cycle is detected.
Return Result: If n
becomes 1 during the process, return True
. If a cycle is detected (where n
has already been seen), return False
.
O(log n). Each transformation step involves computing the sum of squares of digits, which is proportional to the number of digits in n
.
O(log n) due to the space used by the seen
set, which stores numbers encountered during the transformation process.
class Solution {
public:
bool isHappy(int n) {
if (n == 1 || n == 7) {
return true;
}
while (n > 9) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
n = sum;
if (n == 1 || n == 7) {
return true;
}
}
return n == 1 || n == 7;
}
};
class Solution:
def isHappy(self, n: int) -> bool:
def get_next(n):
return sum(int(digit) ** 2 for digit in str(n))
seen = set()
while n != 1 and n not in seen:
seen.add(n)
n = get_next(n)
return n == 1
class Solution {
public boolean isHappy(int n) {
if (n == 1 || n == 7) {
return true;
}
while (n > 9) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
n = sum;
if (n == 1 || n == 7) {
return true;
}
}
return n == 1 || n == 7;
}
}
var isHappy = function (n) {
if (n == 1 || n == 7) {
return true;
}
while (n > 9) {
let arr = n.toString().split("").map(Number);
let powered = arr.map((num) => {
return Math.pow(num, 2);
});
n = powered.reduce(function (accumulator, currentValue) {
return accumulator + currentValue;
}, 0);
if (n == 1 || n == 7) {
return true;
}
}
if (n != 1 || n != 7) {
return false;
}
};