Easy 0 solved 0% acceptance

Distinct Powers

Count the different values of a to the power b for a and b in a range.

What you'll learn

  • Reduce a base to its smallest root
  • Compare huge powers without computing them
  • Count unique values with a set

Problem

Take every a and every b from lo to hi and compute a^b. Some values repeat, like 2^4 = 4^2 = 16. Count how many different values there are. The values are huge, but you never need them: write a as r^k where r is not itself a perfect power, and a^b = r^(k × b). Two powers are equal exactly when they share the same r and the same exponent k × b.

Implement distinct_powers(lo, hi).

Input

lo: The smallest base and exponent.

hi: The largest base and exponent.

Output

Return the number of distinct values of a^b with lo ≤ a ≤ hi and lo ≤ b ≤ hi.

Constraints

2 ≤ lo ≤ hi ≤ 100

Examples

Example 1
Input:
lo = 2
hi = 4

Expected output:
expected = 8
Input:
long long lo = 2;
long long hi = 4;

Expected output:
long long expected = 8;
Input:
long lo = 2;
long hi = 4;

Expected output:
long expected = 8;

Explanation

The nine powers are 4, 8, 16, 9, 27, 81, 16, 64, 256. 16 appears twice, so there are 8 distinct values.

Example 2
Input:
lo = 7
hi = 7

Expected output:
expected = 1
Input:
long long lo = 7;
long long hi = 7;

Expected output:
long long expected = 1;
Input:
long lo = 7;
long hi = 7;

Expected output:
long expected = 1;

Explanation

Only 7^7, so 1.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Find the smallest r and largest k with r^k = a.

Hint 2

a^b equals r^(k × b), so the pair (r, k × b) identifies the value.

Hint 3

Put the pairs in a set and count them.

Expected complexity

O((hi − lo)² log hi) time, O((hi − lo)²) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.