69. Sqrt(x)
Sqrt(x) (LeetCode 69) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the On Sorted Array/List subpattern.
How to solve Sqrt(x)
Sqrt(x) is a Binary Search on Sorted Array problem, part of Binary Search Patterns. Master standard binary search on sorted arrays. Learn search insert position, sqrt calculation, and 2D matrix search.
Work towards the solution in these steps:
- Try exploring all integers. (Credits: @annujoshi)
- Use the sorted property of integers to reduced the search space. (Credits: @annujoshi)
The reference solution runs in O(logn) time and O(1) space.
The Sqrt(x) solution and editorial walks through the full approach with reference code.
Problem statement
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
- For example, do not use pow(x, 0.5) in c++ or x 0.5 in python.
Example 1:
Input: x = 4 Output: 2 Explanation: The square root of 4 is 2, so we return 2.
Example 2:
Input: x = 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
Constraints:
- 0 <= x <= 231 - 1
Topics and companies
Topics: Math, Binary Search.
Reported in interviews at Microsoft, Bloomberg, Amazon, Uber, LinkedIn, Google.
How to practise Sqrt(x) on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn) time and O(1) space.
Open Sqrt(x) in the code editor, or read the Sqrt(x) editorial for a worked solution with its approach and complexity analysis.
Where Sqrt(x) sits in the DSA pattern sheet
Problems related to Sqrt(x)
Other problems that use the same On Sorted Array/List and Binary Search Patterns techniques:
- Binary Search — Easy, same subpattern
- First Bad Version — Easy, same subpattern
- Guess Number Higher or Lower — Easy, same subpattern
- Kth Missing Positive Number — Easy, same subpattern
- Search a 2D Matrix — Medium, same subpattern
- Search Insert Position — Easy, same subpattern
Sqrt(x) FAQ
What is the LeetCode number of Sqrt(x)?
Sqrt(x) is LeetCode problem 69, rated Easy.
What pattern is used to solve Sqrt(x)?
Sqrt(x) is a Binary Search on Sorted Array problem. It belongs to the Binary Search Patterns pattern, in the On Sorted Array/List subpattern.
What is the time complexity of Sqrt(x)?
The reference solution runs in O(logn) time and O(1) space.
Which companies ask Sqrt(x)?
Sqrt(x) has been reported in interviews at Microsoft, Bloomberg, Amazon, Uber, LinkedIn, Google.