Happy Number

MediumMathNumber-TheoryCycle-DetectionHashing5 hidden tests

Starting from n, repeatedly replace it with the sum of the squares of its digits. A number is happy if this process eventually reaches 1; otherwise it falls into a cycle that never includes 1.

Input format

One line: a positive integer n.

Output format

Print YES if n is happy, otherwise NO.

Constraints

1 <= n <= 1000000000

Examples

Example 1

Input

Expected

YES

Explanation

1^2+9^2=82, 8^2+2^2=68, 6^2+8^2=100, 1^2+0+0=1. It reaches 1, so YES.

Example 2

Input

Expected

NO

Explanation

The sequence from 2 cycles (4,16,37,...) and never reaches 1, so NO.

Ready to solve this?

Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.

Sign in to solve →