Happy numbers
Limits: 4 sec., 256 MiB
This statement was translated automatically from Ukrainian.
None of Zenyk’s and Marichka’s classmates joined their preparation for the EIT, because today they are participating in the district informatics Olympiad. Therefore, Zenyk and Marichka will prepare together. Their first exam will be mathematics, so they will start their preparation with it. They opened the mathematics syllabus, and the first topic they encountered was lucky numbers. It’s a good thing that the school library has a collection of problems on this topic.
Zenyk and Marichka invite you to solve one of the problems from the collection as well.
It is known that a lucky number is a number whose decimal representation contains only fours and sevens. For example, the numbers 4, 7, 47, 7777, and 4744474 are lucky.
A rather happy number (happier number) is defined as a natural number whose sum of digits is lucky.
Calculate the number of rather happy numbers not exceeding \(n\).
Input
The single line contains a single integer \(n\).
Output
In the single line, print a single integer — the number of rather happy numbers not exceeding \(n\).
Constraints
\(1 \le n \le 10^6\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 47 | 10 |
Notes
All rather happy numbers not exceeding 47: 4, 7, 13, 16, 22, 25, 31, 34, 40, 43.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|