Count Lucky Numbers in an Inclusive Range
Company: Target
Role: Backend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## Count Lucky Numbers in an Inclusive Range
### Problem
A positive integer `x` is lucky when it is divisible by `floor(sqrt(x))`.
Implement `countLuckyNumbers(left, right) -> count`, returning how many lucky integers lie in the inclusive interval `[left, right]`.
### Function Contract
- `left` and `right` are decimal strings so every supported value is represented exactly in JavaScript and in JSON.
- The strings contain digits only, have no leading zeroes, and represent `1 <= left <= right <= 10^18`.
- Return `count` as a nonnegative integer. It can be as large as `2,999,999,998`, so use a signed 64-bit integer where a language's default integer is only 32 bits; JavaScript can represent this result exactly as a `Number`.
### Examples
```text
left = "1"
right = "8"
count = 6
```
```text
left = "5"
right = "7"
count = 1
```
```text
left = "15"
right = "16"
count = 2
```
```text
left = "999999999999999999"
right = "1000000000000000000"
count = 2
```
### Requirements
- Do not scan every integer in the interval.
- Use exact integer arithmetic. If a floating-point square root is used as an initial estimate, correct it before relying on the result.
- Aim for `O(log right)` time or better and `O(1)` auxiliary space, excluding fixed-width integer representation.
- Explain how to count an interval by subtracting two inclusive-prefix counts.
```hint Fix the square-root bucket
For one value `k = floor(sqrt(x))`, inspect the integers from `k * k` through `(k + 1) * (k + 1) - 1` and ask how many multiples of `k` can occur there.
```
### Discussion Prompts
1. Why is converting the decimal inputs to an IEEE-754 number unsafe near `10^18`?
2. What changes at a perfect square?
3. How do you define the prefix count at zero when evaluating `left - 1`?
Quick Answer: Count positive integers in an inclusive range that are divisible by their floored square root. The task requires exact arithmetic up to very large decimal inputs, efficient bucket reasoning, perfect-square boundaries, prefix-count composition, and avoidance of unsafe floating-point assumptions.
A positive integer `x` is **lucky** when it is divisible by `floor(sqrt(x))`, the integer square root of `x`.
Implement `countLuckyNumbers(left, right)`, returning how many lucky integers lie in the inclusive interval `[left, right]`.
### Input
`left` and `right` are **decimal strings**, so every supported value is represented exactly in JavaScript and in JSON. Each string contains digits only and has no leading zeroes. They represent integers with `1 <= left <= right <= 10^18`.
### Output
Return `count`, the number of lucky integers `x` with `left <= x <= right`, as a single nonnegative integer. The answer is unique for every input: there is no ordering or tie-breaking choice to make. The count can be as large as `2,999,999,998`, so return a signed 64-bit integer in languages whose default integer is only 32 bits (`long` in Java, `long long` in C++). JavaScript represents this result exactly as a `Number`.
### Examples
Example 1:
```text
left = "1"
right = "8"
count = 6
```
The lucky values in `[1, 8]` are `1, 2, 3, 4, 6, 8`. For `x = 6`, `floor(sqrt(6)) = 2` and `6 % 2 == 0`. For `x = 5`, `floor(sqrt(5)) = 2` and `5 % 2 == 1`, so `5` is not lucky.
Example 2:
```text
left = "5"
right = "7"
count = 1
```
Only `6` is lucky here; `5` and `7` both leave a remainder of `1` when divided by `floor(sqrt(x)) = 2`.
Example 3:
```text
left = "15"
right = "16"
count = 2
```
`floor(sqrt(15)) = 3` divides `15`, and `floor(sqrt(16)) = 4` divides `16`. The interval crosses a perfect square, where the integer square root increments.
Example 4:
```text
left = "999999999999999999"
right = "1000000000000000000"
count = 2
```
Near `10^18` an IEEE-754 square root is not trustworthy: `Math.sqrt` of `10^18 - 1` rounds up to `10^9`, while the true `floor(sqrt(10^18 - 1))` is `999999999`.
### Requirements
- Do not scan every integer in the interval; the interval can contain `10^18` values.
- Use exact integer arithmetic. A floating-point square root may be used as an initial estimate, but correct it before relying on the result.
- Aim for `O(log right)` time or better and `O(1)` auxiliary space, excluding the fixed-width integer representation.
Constraints
- left and right are decimal strings containing digits only, with no leading zeroes
- 1 <= left <= right <= 10^18 (as the integers the strings represent)
- The returned count is a nonnegative integer and can be as large as 2,999,999,998
- Because 2,999,999,998 exceeds 2^31 - 1, return a signed 64-bit integer where the language's default integer is 32 bits (long in Java, long long in C++)
- Target O(log right) time or better and O(1) auxiliary space, excluding the fixed-width integer representation
- The interval can hold up to 10^18 values, so a per-integer scan is not acceptable
Examples
Input: ("1", "8")
Expected Output: 6
Input: ("5", "7")
Expected Output: 1
Hints
- Counting a range is easier than it looks if you can count a prefix: if f(n) is the number of lucky integers in [1, n], the answer is f(right) - f(left - 1). Decide what f should return at 0.
- Group the integers by the value k = floor(sqrt(x)). All the x with the same k form the run k*k through (k + 1)*(k + 1) - 1. Ask how many multiples of k that run can contain -- the answer does not depend on k.
- A double cannot represent every integer up to 10^18, so a floating-point square root can land one off near the top of the range. Treat it as a seed and repair it, comparing with division rather than a product so the repair cannot overflow.