Peculiar Numbers
We define a number N as peculiar if it is divisible by the integer part of its square root. Formally, N is peculiar if:
\(N \bmod \lfloor \sqrt{N}\rfloor = 0\)
Given a range [L, R], implement a function to determine how many integers within this range (inclusive) are peculiar.
Examples
Example 1
Input: L=1, R=10
Output: 7
Explanation: The peculiar numbers between 1 and 10 are 1,2,3,4,6,8,9.
Example 2
Input: L=50, R=60
Output: 1
Explanation: The only peculiar number between 50 and 60 is 56.
Example 3
Input: L=100, R=120
Output: 3
Explanation: The peculiar numbers between 100 and 120 are 100,110,120.
Follow-Up
It’s not hard to come up with a O(√R) approach, but can you design a constant-time solution?
Ideas:
1. The range of divisors to check are contiguous floor(sqrt(L)) to floor(sqrt(R)).
let l = floor(sqrt(L)) and r = floor(sqrt(R))
2. Then all numbers from l+1 to r-1 have exactly 3 numbers they divide. We can get this by looking at the numbers they test in the range L to R, for any t in l to r. we need to check numbers in range [(t+1)^2 -1 , t^2]. Then count of numbers divisible by t in this range is floor(3 + 1/t) = 3
3. Finally we need to handle boundary cases with l and r:
For l : ((l+1)^2 - L)/l + 1
For r: (R - r^2)/r + 1
So the final answer will be
3*( r - l - 1) + ((l+1)^2 - L)/l +1 (add 1 if l is not 1) + (R - r^2)/r + 1