Integer Square Roots
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given an array nums of non-negative integers, return for each nums[i] the largest integer with
nums[i], i.e. , in the same order.
Values go up to , so use 64-bit integers, and beware that a floating-point square root can be off for large values.
Examples
| nums | result |
|---|---|
[4, 8, 0] | [2, 2, 0] |
[1000000000000000000] | [1000000000] |
[15, 16, 17, 99] | [3, 4, 4, 9] |
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(nums: long[]) → long[]
Constraints
-
nums.length -
nums[i]
Expected complexity
- Time
- O(Q log X)
- Space
- O(Q)
Examples
| nums | Expected |
|---|---|
[4,8,0] | [2,2,0] |
[1000000000000000000] | [1000000000] |
[15,16,17,99] | [3,4,4,9] |
Hint
Hint
"" flips from true to false exactly once as grows, so binary search the boundary between lo = 0 and
hi = 10^9 + 1 (about 30 steps per value; mid * mid stays within 64 bits). If you use a floating-point sqrt, correct
the result afterwards (decrease while r * r > x, increase while (r + 1)^2 <= x): a double cannot represent integers
near exactly. Counting r up one by one is up to steps per value and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1230 ms | derived |
| Java 25 | 1396 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |