Square Root of a Number
EasyLargest m with m·m ≤ x
Guess the square root, square your guess, and adjust higher or lower — halving the range each time.
The idea
The floor of √x is the biggest integer whose square doesn't exceed x — a monotone condition, so binary search the answer.
1
2
3
4
5
0
1
2
3
4
Step 1 of 7. Brute force: try 1, 2, 3, … until the square passes 28. Values: 1, 2, 3, 4, 5.
1/7
Brute force
timeO(√n)spaceO(1)
Count up.
1let k = 1;2while (k * k <= n) k++;3// k is now the first value whose square overshoots4return k - 1;Input
- array
- [1, 2, 3, 4, 5]
Memory
- k
- —
Output
- floor √
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 36
- Output:
- 6
- Explanation:
- 6 x 6 = 36 exactly.
Example 2
- Input:
- n = 28
- Output:
- 5
- Explanation:
- 5x5=25 <= 28 < 36=6x6, so the floor is 5.
Example 3
- Input:
- n = 1
- Output:
- 1
- Explanation:
- The square root of 1 is 1.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.