Problem #63 medium
Powerful Digit Counts
The -digit number, , is also a fifth power. Similarly, the -digit number, , is a ninth power.
How many -digit positive integers exist which are also an th power?
Implementations
#include <iostream>#include <cmath>
int powerful_digit_counts() { int count = 0; for (int a = 1; a <= 9; ++a) { double log_a = std::log10(static_cast<double>(a)); int max_n = static_cast<int>(1.0 / (1.0 - log_a)); count += max_n; } return count;}
#if ! defined UNITTEST_MODEint main(int argc, char const *argv[]) { std::cout << powerful_digit_counts() << std::endl;}#endif View on GitHub
O(1) time complexity
Solution Notes
Mathematical Background
This problem asks for the count of n-digit numbers that are also nth powers.
Algorithm Analysis
Use logarithmic calculation to find the maximum n for each base a from 1 to 9, where a^n has exactly n digits.
Performance Analysis
- Time Complexity: O(1) - constant loop over 9 values
- Space Complexity: O(1) - no additional space
- Execution Time: Instantaneous
- Scalability: Not applicable, fixed computation
Key Insights
- For base a, the maximum n is floor(1 / (1 - log10(a)))
- Only bases 1-9 can produce n-digit nth powers for n > 1
- The answer is 49
Educational Value
This problem teaches:
- Logarithmic properties for digit counting
- Mathematical bounds and inequalities
- Efficient computation without iteration