202. Happy Number
Tags:
Easy
Skills:
Hashmap
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu xác định xem một số nguyên dương n có phải là “happy number” hay không.
Một số được gọi là Happy number nếu lặp lại quá trình sau sẽ dẫn đến 1
Thay thế số đó bằng tổng bình phương cá chữ số của nó. Nếu quá trình này rơi vào vòng lặp vô tận mà không bao giờ đạt đến 1, thì số đó không phải là happy number.
Approach - Set
set để lưu các số đã xuất hiện trong quá trình tính toánSolution - set
1function isHappy(n: number): boolean {
2 function getNext(num: number): number {
3 let sum =0 ;
4 while(num > 0) {
5 const digit = num % 10;
6 sum += digit * digit;
7 num = Math.floor(num / 10);
8 }
9
10 return sum;
11 }
12
13 const seen: Set<number> = new Set();
14 while(n!==1) {
15 n = getNext(n);
16 if(seen.has(n)) return false;
17 seen.add(n);
18 }
19
20 return true;
21};Approach - Two pointer (Floyd’s cycle detection)
Time and space complexity:
TC: O(logn)
SC: O(1)
Solution - two pointer
1function isHappy(n: number): boolean {
2 function getNext(num: number): number {
3 let sum = 0;
4 while (num > 0) {
5 const digit = num % 10;
6 sum += digit * digit;
7 num = Math.floor(num / 10)
8 }
9
10 return sum;
11 }
12
13 let slow = getNext(n);
14 let fast = getNext(getNext(n))
15 while (slow !== fast) {
16 slow = getNext(slow);
17 fast = getNext(getNext(fast));
18 }
19
20 return fast === 1;
21};