Skip to content

Latest commit

 

History

History
12 lines (9 loc) · 628 Bytes

README.md

File metadata and controls

12 lines (9 loc) · 628 Bytes
Raw

Task

Link

Implement int sqrt(int x). Compute and return the square root of x.

Presentation

Solutions

  • Wrap a set of n^2 values into an iterator, and use binary search from standard library to find a solution of n^2 == x in O(1) memory and O(log n) time. Solution.
  • Use binary search to find sqrt(x). Solution1, solution2.
  • Save O(sqrt n) possible solutions into a container, and use a custom comparator. Assume that value we seek is only used as a first argument in comparison.