Problem · Math
Count Power Products in Range
Learn this problem● Easy
IBMFULLTIMEOA
See IBM hiring insightsIBMFULLTIMEOAProblem statement
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
countPowerProductsInRange(low: long, high: long) → int Complete the function countPowerProductsInRange in the editor below.
countPowerProductsInRange has the following parameters:
long low: the lower bound of the rangelong high: the upper bound of the range
Returns int: the number of integers in [low, high] that can be expressed as 3x * 5y.
Examples
Example 1
low = 1high = 15return = 5The valid numbers in the range are 1, 3, 5, 9, 15. Therefore, the answer is 5.
Example 2
low = 16high = 100return = 5The valid numbers in the range are 25, 27, 45, 75, 81. Therefore, the answer is 5.
Constraints
- The source thread did not provide explicit numeric bounds.
xandyare non-negative integers.- Only values within the inclusive range
[low, high]should be counted. - Implementations should avoid overflow when generating powers of
3and5.