# Square root of an integer

Given an integer x, find it’s square root. If x is not a perfect square, then return floor(√x).

Examples :

```Input: x = 4
Output: 2
Explanation:  The square root of 4 is 2.

Input: x = 11
Output: 3
Explanation:  The square root of 11 lies in between
3 and 4 so floor of the square root is 3.```

There can be many ways to solve this problem. For example Babylonian Method is one way.
Simple Approach: To find the floor of the square root, try with all-natural numbers starting from 1. Continue incrementing the number until the square of that number is greater than the given number.

• Algorithm:
1. Create a variable (counter) and take care of some base cases, i.e when the given number is 0 or 1.
2. Run a loop until , where n is the given number. Increment i by 1.
3. The floor of the square root of the number is
• Implementation:

## C++

`#includevàlt;bits/stdc++.hvàgt;`

`using` `namespace` `std;`

`int` `floorSqrt(``int` `x)`

`{`

`    `

`    ``if` `(x == 0 || x == 1)`

`    ``return` `x;`

`    `

`    `

`    ``int` `i = 1, result = 1;`

`    ``while` `(result <= x)`

`    ``{`

`      ``i++;`

`      ``result = i * i;`

`    ``}`

`    ``return` `i - 1;`

`}`

`int` `main()`

`{`

`    ``int` `x = 11;`

`    ``cout << floorSqrt(x) << endl;`

`    ``return` `0;`

`}`

## Java

`class` `GFG {`

`    `

`    `

`    ``static` `int` `floorSqrt(``int` `x)`

`    ``{`

`        `

`        ``if` `(x == ` `|| x == ``1``)`

`            ``return` `x;`

`        `

`        `

`        ``int` `i = ``1``, result = ``1``;`

`        `

`        ``while` `(result <= x) {`

`            ``i++;`

`            ``result = i * i;`

`        ``}`

`        ``return` `i - ``1``;`

`    ``}`

`    `

`    ``public` `static` `void` `main(String[] args)`

`    ``{`

`        ``int` `x = ``11``;`

`        ``System.out.print(floorSqrt(x));`

`    ``}`

`}`

## Python3

`def` `floorSqrt(x):`

`    `

`    ``if` `(x ``=``=` `or` `x ``=``=` `1``):`

`        ``return` `x`

`    `

`    `

`    ``i ``=` `1``; result ``=` `1`

`    ``while` `(result <``=` `x):`

`    `

`        ``i ``+``=` `1`

`        ``result ``=` `i ``*` `i`

`    `

`    ``return` `i ``-` `1`

`x ``=` `11`

`print``(floorSqrt(x))`

## C#

`using` `System;`

`class` `GFG`

`{`

`    `

`    `

`    ``static` `int` `floorSqrt(``int` `x)`

`    ``{`

`        `

`        ``if` `(x == 0 || x == 1)`

`            ``return` `x;`

`        `

`        `

`        `

`        ``int` `i = 1, result = 1;`

`        `

`        ``while` `(result <= x)`

`        ``{`

`            ``i++;`

`            ``result = i * i;`

`        ``}`

`        ``return` `i - 1;`

`    ``}`

Xem Thêm  Cách phát video trực tuyến bằng HTML - mã html để phát video

`    `

`    ``static` `public` `void` `Main ()`

`    ``{`

`        ``int` `x = 11;`

`        ``Console.WriteLine(floorSqrt(x));`

`    ``}`

`}`

## PHP

`<?php`

`function` `floorSqrt(``\$x``)`

`{`

`    `

`    ``if` `(``\$x` `== 0 || ``\$x` `== 1)`

`    ``return` `\$x``;`

`    `

`    `

`    `

`    ``\$i` `= 1;`

`    ``\$result` `= 1;`

`    ``while` `(``\$result` `<= ``\$x``)`

`    ``{`

`        ``\$i``++;`

`        ``\$result` `= ``\$i` `* ``\$i``;`

`    ``}`

`    ``return` `\$i` `- 1;`

`}`

`\$x` `= 11;`

`echo` `floorSqrt(``\$x``), ``"n"``;`

`?>`

## Javascript

`<scriptvàgt;`

`function` `floorSqrt(x)`

`{`

`    `

`    `

`    ``if` `(x == 0 || x == 1)`

`        ``return` `x;`

`    `

`    `

`    `

`    ``let i = 1;`

`    ``let result = 1;`

`    `

`    ``while` `(result <= x)`

`    ``{`

`        ``i++;`

`        ``result = i * i;`

`    ``}`

`    ``return` `i - 1;`

`}`

`let x = 11;`

`document.write(floorSqrt(x));`

`</scriptvàgt;`

Output :

`3`
• Complexity Analysis:
• Time Complexity: O(√ n).
Only one traversal of the solution is needed, so the time complexity is O(√ n).
• Space Complexity: O(1).
Constant extra space is needed.

Better Approach: The idea is to find the largest integer whose square is less than or equal to the given number. The idea is to use Binary Search to solve the problem. The values of i * i is monotonically increasing, so the problem can be solved using binary search.

• Algorithm:
1. Take care of some base cases, i.e when the given number is 0 or 1.
2. Create some variables, lowerbound , upperbound , where n is the given number, and to store the answer.
3. Run a loop until , the search space vanishes
4. Test if the square of mid () is less than or equal to n, If yes then search for a larger value in second half of search space, i.e l = mid + 1, cập nhật ans = mid
5. Else if the square of mid is more than n then search for a smaller value in first half of search space, i.e r = mid – 1
6. Print the value of answer ( )
• Implementation:

## C++

`#include <iostreamvàgt;`

`using` `namespace` `std;`

`int` `floorSqrt(``int` `x)`

`{`

`    `

`    ``if` `(x == 0 || x == 1)`

`        ``return` `x;`

`    `

`    ``int` `start = 1, end = x/2, ans;`

`    ``while` `(start <= end) {`

`        ``int` `mid = (start + end) / 2;`

`        `

`        ``int` `sqr = mid * mid;`

`        ``if` `(sqr == x)`

`            ``return` `mid;`

Xem Thêm  Cách tạo bảng từ truy vấn SQL - tạo bảng từ truy vấn chọn

`        `

`        `

`        `

`        `

`           `

`                   `

`                           `

`                           `

`                   `

`            `

`           `

`           `

`           `

`            `

`           `

`           `

`        ``if` `(sqr <= x) {`

`            ``start = mid + 1;`

`            ``ans = mid;`

`        ``}`

`        ``else`

`            ``end = mid - 1;`

`    ``}`

`    ``return` `ans;`

`}`

`int` `main()`

`{`

`    ``int` `x = 20221;`

`    ``cout << floorSqrt(x) << endl;`

`    ``return` `0;`

`}`

## Java

`public` `class` `Check`

`{`

`    ``public` `static` `int` `floorSqrt(``int` `x)`

`    ``{`

`        `

`        ``if` `(x == ` `|| x == ``1``)`

`            ``return` `x;`

`        `

`        ``long` `start = ``1``, end = x, ans=``;`

`        ``while` `(start <= end)`

`        ``{`

`            ``int` `mid = (start + end) / ``2``;`

`            `

`            ``if` `(mid*mid == x)`

`                ``return` `(``int``)mid;`

`            `

`            `

`            ``if` `(mid*mid < x)`

`            ``{`

`                ``start = mid + ``1``;`

`                ``ans = mid;`

`            ``}`

`            ``else`

`                ``end = mid-``1``;`

`        ``}`

`        ``return` `(``int``)ans;`

`    ``}`

`    `

`    ``public` `static` `void` `main(String args[])`

`    ``{`

`        ``int` `x = ``11``;`

`        ``System.out.println(floorSqrt(x));`

`    ``}`

`}`

## Python3

`def` `floorSqrt(x) :`

`    `

`    ``if` `(x ``=``=` `or` `x ``=``=` `1``) :`

`        ``return` `x`

` `

`    `

`    ``start ``=` `1`

`    ``end ``=` `x  `

`    ``while` `(start <``=` `end) :`

`        ``mid ``=` `(start ``+` `end) ``/``/` `2`

`        `

`        `

`        ``if` `(mid``*``mid ``=``=` `x) :`

`            ``return` `mid`

`            `

`        `

`        `

`        `

`        ``if` `(mid ``*` `mid < x) :`

`            ``start ``=` `mid ``+` `1`

`            ``ans ``=` `mid`

`            `

`        ``else` `:`

`            `

`            `

`            ``end ``=` `mid``-``1`

`            `

`    ``return` `ans`

`x ``=` `11`

`print``(floorSqrt(x))`

`    `

## C#

`using` `System;`

`class` `GFG`

`{`

`    ``public` `static` `int` `floorSqrt(``int` `x)`

`    ``{`

`        `

`        ``if` `(x == 0 || x == 1)`

`            ``return` `x;`

`        `

`        `

`        ``int` `start = 1, end = x, ans = 0;`

`        ``while` `(start <= end)`

`        ``{`

`            ``int` `mid = (start + end) / 2;`

`            `

`            `

`            ``if` `(mid * mid == x)`

`                ``return` `mid;`

`            `

`            `

`            `

`            `

`            ``if` `(mid * mid < x)`

`            ``{`

`                ``start = mid + 1;`

`                ``ans = mid;`

`            ``}`

`            `

`            `

`            `

`            ``else`

`                ``end = mid-1;`

`        ``}`

`        ``return` `ans;`

`    ``}`

`    `

`    ``static` `public` `void` `Main ()`

`    ``{`

`        ``int` `x = 11;`

`        ``Console.WriteLine(floorSqrt(x));`

`    ``}`

`}`

Xem Thêm  Pandas For Loop - vòng lặp while ở gấu trúc

## PHP

`<?php`

`function` `floorSqrt(``\$x``)`

`{`

`    `

`    ``if` `(``\$x` `== 0 || ``\$x` `== 1)`

`    ``return` `\$x``;`

`    `

`    `

`    ``\$start` `= 1; ``\$end` `= ``\$x``; ``\$ans``;`

`    ``while` `(``\$start` `<= ``\$end``)`

`    ``{`

`        ``\$mid` `= (``\$start` `+ ``\$end``) / 2;`

`        `

`        ``if` `(``\$mid` `* ``\$mid` `== ``\$x``)`

`            ``return` `\$mid``;`

`        `

`        `

`        `

`        ``if` `(``\$mid` `* ``\$mid` `< ``\$x``)`

`        ``{`

`            ``\$start` `= ``\$mid` `+ 1;`

`            ``\$ans` `= ``\$mid``;`

`        ``}`

`        `

`        `

`        `

`        ``else`

`            ``\$end` `= ``\$mid``-1;    `

`    ``}`

`    ``return` `\$ans``;`

`}`

`\$x` `= 11;`

`echo` `floorSqrt(``\$x``), ``"n"``;`

`?>`

## Javascript

`<scriptvàgt;`

`    `

`function` `floorSqrt(x)`

`{`

`    `

`    ``if` `(x == 0 || x == 1)`

`    ``return` `x;`

`    `

`    `

`    ``let start = 1;`

`    ``let end = x;`

`    ``let ans;`

`    ``while` `(start <= end)`

`    ``{`

`        ``let mid = (start + end) / 2;`

`        `

`        ``if` `(mid * mid == x)`

`            ``return` `mid;`

`        `

`        `

`        `

`        ``if` `(mid * mid < x)`

`        ``{`

`            ``start = mid + 1;`

`            ``ans = mid;`

`        ``}`

`        `

`        `

`        `

`        ``else`

`            ``end = mid-1;    `

`    ``}`

`    ``return` `ans;`

`}`

`let x = 11;`

`document.write(floorSqrt(x) +  ``"<br>"``);`

`</scriptvàgt;`

Output :

`142`
• Complexity Analysis:
• Time complexity: O(log n).
The time complexity of binary search is O(log n).
• Space Complexity: O(1).
Constant extra space is needed.

Thanks to Gaurav Ahirwar for suggesting above method.
chú ý: The Binary Search can be further optimized to start with ‘start’ = 0 and ‘end’ = x/2. Floor of square root of x cannot be more than x/2 when x > 1.
Thanks to vinit for suggesting above optimization.