Lets Code Everyday - Day4
Question - 4 :-
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
First approach:
class Solution {
public boolean isHappy(int n) {
int sum = 0;
while (n != 1 && n != 4) {
while (n != 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
n = sum;
sum = 0;
}
return n == 1;
}
}
Here is a step by step explanation of how the code works:
The function
isHappytakes an integernas input and returns a boolean value.The integer variable
sumis initialized to 0.The while loop checks if the input
nis not equal to 1 and 4.Inside the while loop, another while loop is used to calculate the sum of squares of the digits of the number
n.The integer variable
digitis initialized to the remainder obtained by dividingnby 10 (gives us the last digit of the number).The variable
sumis updated by adding the square ofdigitto it.The variable
nis updated by dividingnby 10, which removes the last digit fromn.Steps 5-7 are repeated until
nbecomes 0.The value of
nis updated to the value ofsum.The value of
sumis reset to 0.Steps 4-10 are repeated until the value of
nbecomes either 1 or 4.If the value of
nis 1, the function returnstrue, indicating that the inputnis a Happy Number.If the value of
nis 4, the function returnsfalse, indicating that the inputnis not a Happy Number.The end result is a boolean value that tells us whether the input
nis a Happy Number or not.
The time complexity of the code is O(k log k), where k is the number of digits in n.
The space complexity of the code is O(1), i.e., constant space, as only a constant amount of additional memory is required to store the variable sum. The memory used for storing n and digit is reused in each iteration of the while loop.
Second approach:
class Solution {
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = getNext(n);
}
return n == 1;
}
private int getNext(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
}
Here is a step-by-step explanation of how the code works:
The function
isHappytakes an integernas input and returns a boolean value.A new HashSet called
seenis initialized to keep track of the numbers that have been seen during the computation.The while loop checks if the input
nis not equal to 1 and ifnis not already present in theseenset.Inside the while loop, the value of
nis added to theseenset to mark it as seen.The value of
nis updated to the next number in the Happy Number sequence using thegetNextmethod.The
getNextmethod calculates the sum of squares of the digits of the numbernusing the same approach as the previous code you provided.The value of
sumis returned from thegetNextmethod.Steps 5-7 are repeated until the value of
nbecomes either 1 or is already present in theseenset.If the value of
nis 1, the function returnstrue, indicating that the inputnis a Happy Number.The end result is a boolean value that tells us whether the input
nis a Happy Number or not.
The time complexity of this code is also O(k), where k is the number of digits in n. The space complexity is O(k) as well, since the seen set can contain up to k elements in the worst-case scenario where every number in the Happy Number sequence is distinct.
However, this implementation might be more efficient in practice, since it can avoid unnecessary iterations if a cycle is detected in the Happy Number sequence.
