Last updated on July 15th, 2024 at 04:28 am
Here, We see Happy Number LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.
List of all LeetCode Solution
Topics
Hash Table, Math
Companies
Airbnb, Twitter, Uber
Level of Question
Easy
Happy Number LeetCode Solution
Table of Contents
Problem Statement
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
1. Happy Number Leetcode Solution C++
class Solution {
public:
int solve(int n) {
int sum = 0;
while(n > 0) {
int r = n%10;
sum += r*r;
n /= 10;
}
return sum;
}
bool isHappy(int n) {
int slow = n, fast = n;
do {
slow = solve(slow);
fast = solve(solve(fast));
if(fast == 1) return 1;
} while(slow != fast);
return 0;
}
};
1.1 Explanation
- solve Function: Computes the sum of the squares of the digits of n.
- isHappy Function:
- Uses Floyd’s Cycle Detection Algorithm (tortoise and hare) to detect cycles.
- slow and fast pointers are used, where slow moves one step at a time and fast moves two steps at a time.
- If fast reaches 1, the number is happy.
- If slow and fast meet (cycle detected) and they are not 1, the number is not happy.
1.2 Time Complexity
- O(k), where k is the number of digits in the number and steps required to reach 1 or detect a cycle.
1.3 Space Complexity
- O(1), since we only use a few variables.
2. Happy Number Leetcode Solution Java
class Solution {
public boolean isHappy(int n) {
if(n<=0) return false;
while(true){
int sum=0;
while(n!=0){
sum+=(n%10)*(n%10);
n=n/10;
}
if(sum/10==0){
if(sum==1||sum==7) return true;
else return false;
}
n=sum;
}
}
}
2.1 Explanation
- Happy Number Check:
- Computes the sum of the squares of the digits repeatedly.
- If the sum becomes a single digit, check if it is 1 or 7 (since 7 is a known happy number).
2.2 Time Complexity
- O(k), where k is the number of digits in the number and steps required to reach 1 or detect an unhappy number.
2.3 Space Complexity
- O(1), since we only use a few variables.
3. Happy Number Leetcode Solution JavaScript
var isHappy = function(n) {
var seen = {};
while (n !== 1 && !seen[n]) {
seen[n] = true;
n = sumOfSquares(n);
}
return n === 1 ? true : false;
};
function sumOfSquares(numString) {
return numString.toString().split('').reduce(function(sum, num) {
return sum + Math.pow(num, 2);
}, 0);
};
3.1 Explanation
- Happy Number Check:
- Uses a dictionary seen to track numbers that have been seen to detect cycles.
- Computes the sum of the squares of the digits of n using the sumOfSquares function.
- If a number is seen again, a cycle is detected and false is returned.
3.2 Time Complexity
- O(k), where k is the number of digits in the number and steps required to reach 1 or detect a cycle.
3.3 Space Complexity
- O(k) for storing numbers in the seen dictionary.
4. Happy Number Leetcode Solution Python
class Solution(object):
def isHappy(self, n):
total = 0
for digit_str in str(n):
digit = int(digit_str)
total += digit * digit
if total == 1 or total == 7:
return True
else:
if total < 10 or total == 0:
return False
else:
return self.isHappy(total)
4.1 Explanation
- The method isHappy computes the sum of the squares of the digits of n.
- If the sum is 1 or 7, it returns True.
- If the sum is a single-digit number other than 1 or 7, it returns Fals
e. - Otherwise, it recursively calls isHappy with the sum.
4.2 Time Complexity
- O(nlogn).
4.3 Space Complexity
- O(n) due to the recursion stack.