FastPrepFastPrep
Problem Brief

Count Power Products in Range

FULLTIMEOA

Given two integers low and high, count how many integers in the inclusive range [low, high] can be written in the form 3x * 5y, where x and y are non-negative integers.

Each valid value should be counted once, even if there is only one way to generate it. The value 1 is valid because 1 = 30 * 50.

Function Description

Complete the function countPowerProductsInRange in the editor below.

countPowerProductsInRange has the following parameters:

  1. long low: the lower bound of the range
  2. long high: the upper bound of the range

Returns

int: the number of integers in [low, high] that can be expressed as 3x * 5y.

1Example 1

Input
low = 1, high = 15
Output
5
Explanation

The valid numbers in the range are 1, 3, 5, 9, 15. Therefore, the answer is 5.

2Example 2

Input
low = 16, high = 100
Output
5
Explanation

The valid numbers in the range are 25, 27, 45, 75, 81. Therefore, the answer is 5.

Constraints

Limits and guarantees your solution can rely on.

The source thread did not provide explicit numeric bounds.

  • x and y are non-negative integers.
  • Only values within the inclusive range [low, high] should be counted.
  • Implementations should avoid overflow when generating powers of 3 and 5.
public int countPowerProductsInRange(long low, long high) {
    // write your code here
}
Input

low

1

high

15

Output

5

Sign in to submit your solution.