RabbitNumber
SRM 484 · 2010-03-12 · by rng_58
SRM 484 · 2010-03-12 · by rng_58 · Brute Force, Math
Problem Statement
Problem Statement
When cat Taro and rabbit Hanako were practicing hard for SRM 484, they noticed an interesting property of 484. They called it Rabbit Number.
Let S(n) be the sum of the digits of n. For example, S(484) = 4+8+4 = 16 and S(22) = 2+2 = 4. A positive integer x is called a Rabbit Number if S(x*x) = S(x)*S(x). For example, 22 is a Rabbit Number because S(484) = S(22)*S(22).
Return the number of Rabbit Numbers between low and high, inclusive.
Let S(n) be the sum of the digits of n. For example, S(484) = 4+8+4 = 16 and S(22) = 2+2 = 4. A positive integer x is called a Rabbit Number if S(x*x) = S(x)*S(x). For example, 22 is a Rabbit Number because S(484) = S(22)*S(22).
Return the number of Rabbit Numbers between low and high, inclusive.
Constraints
- low will be between 1 and 1,000,000,000, inclusive.
- high will be between low and 1,000,000,000, inclusive.
Examples
0)
22 22 Returns: 1
22 is a Rabbit Number because S(22*22) = S(484) = 16 S(22) * S(22) = 4 * 4 = 16
1)
484 484 Returns: 0
484 is not a Rabbit Number because S(484*484) = S(234256) = 22 S(484) * S(484) = 16 * 16 = 256
2)
1 58 Returns: 12
3)
58 484 Returns: 24
4)
1000000000 1000000000 Returns: 1
Submissions are judged against all 48 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RabbitNumber with a public method int theCount(int low, int high) · 48 test cases · 2 s / 256 MB per case