Factorial Decomposition
Time limit2sMemory limit128 MB
Decide whether a given number up to 10^18 can be written as a sum of factorials of distinct nonnegative integers.
- Level
Medium5 of 10
- Topics
- Greedy, Math, Number theory
- Solved
- No attempts yet
Problem
You are given a nonnegative integer N. Determine whether there are distinct nonnegative integers k_1, k_2, ..., k_M (M >= 1) such that
N = k_1! + k_2! + ... + k_M!.
Each integer may be used at most once. Since 0! and 1! are factorials of different integers, both may be used.
Input
The first line contains the integer N.
Output
Print YES if N can be represented as a sum of factorials of distinct integers. Otherwise, print NO.
Constraints
0 <= N <= 1,000,000,000,000,000,000