Funcia
Lv.1binary-searchmath

Integer Square Roots

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given an array nums of non-negative integers, return for each nums[i] the largest integer rr with r2≤r^2 \le nums[i], i.e. ⌊nums[i]⌋\lfloor \sqrt{\texttt{nums[i]}} \rfloor, in the same order.

Values go up to 101810^{18}, so use 64-bit integers, and beware that a floating-point square root can be off for large values.

Examples

numsresult
[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

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • 0≤0 \le nums[i] ≤1018\le 10^{18}

Expected complexity

Time
O(Q log X)
Space
O(Q)

Examples

numsExpected
[4,8,0][2,2,0]
[1000000000000000000][1000000000]
[15,16,17,99][3,4,4,9]

Hint

Hint

"r2≤xr^2 \le x" flips from true to false exactly once as rr 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 101810^{18} exactly. Counting r up one by one is up to 10910^9 steps per value and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131230 msderived
Java 251396 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.