Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Compute the next number by summing the squares of the digits.
  2. 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");
    }
}

Solve Happy Number online · All practice problems