Practice › Hashing & Two Pointers
Happy Number
Easy · Hashing & Two Pointers · Asked at Amazon, Google, Uber, TCS, Infosys
Starting from n, repeatedly replace the number with the sum of the squares of its digits. If this process reaches 1, n is happy; otherwise it loops forever. Print YES if n is happy, otherwise NO.
Input
A single integer n.
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 2^31 − 1
Store the numbers you have seen in a set — seeing one again means a loop. (Or use slow/fast pointers.)
Example 1
Input
19
Output
YES
Example 2
Input
2
Output
NO
Hints
- Compute the next number by summing the squares of the digits.
- The sequence either reaches 1 or repeats a value. Remember what you have seen.
Approach
Keep a set of visited values. Replace n by the digit-square sum until n == 1 (happy) or n is already in the set (a cycle — not happy). The values drop below 1000 after one step (the largest sum for a 10-digit number is 810), so the loop is short.
Complexity: O(log n) per step, few steps · O(1) space in practice
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
set<long long> seen;
while (n != 1 && !seen.count(n)) {
seen.insert(n);
long long s = 0;
for (long long x = n; x > 0; x /= 10) s += (x % 10) * (x % 10);
n = s;
}
cout << (n == 1 ? "YES" : "NO") << "\n";
return 0;
}Python solution
n = int(input())
seen = set()
while n != 1 and n not in seen:
seen.add(n)
n = sum(int(d) ** 2 for d in str(n))
print("YES" if n == 1 else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
long n = new Scanner(System.in).nextLong();
Set<Long> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
long s = 0;
for (long x = n; x > 0; x /= 10) s += (x % 10) * (x % 10);
n = s;
}
System.out.println(n == 1 ? "YES" : "NO");
}
}