Square root
To find the floor of the square root, try with all-natural numbers starting from and continue incrementing the number until the square of that number is greater than the given number. but this will take linear time complexity .
So can we optimize to better complexity , answer is yes , the idea is to find the largest integer i whose square is less than or equal to the given number. The values of i*i is monotonically increasing, so the problem can be solved using binary search.
Below is the code snippet for Square root:
#include <iostream>
int floorSqrt(int x)
{
// Base cases
if (x == 0 || x == 1)
return x;
// Do Binary Search for floor(sqrt(x))
int start = 1, end = x / 2, ans;
while (start <= end) {
int mid = (start + end) / 2;
// If x is a perfect square
int sqr = mid * mid;
if (sqr == x)
return mid;
if (sqr <= x) {
start = mid + 1;
ans = mid;
}
else end = mid - 1;
}
return ans;
}
int main() {
int num1 = 16;
int num2 = 17;
std::cout<< floorSqrt(num1) << std::endl;
std::cout << floorSqrt(num2) << std::endl;
return 0;
}
public class Main {
// Function to find the floor square root of a number
static int floorSqrt(int x) {
// Base cases
if (x == 0 || x == 1)
return x;
int start = 1, end = x / 2, ans = 0;
// Do Binary Search for floor(sqrt(x))
while (start <= end) {
int mid = start + (end - start) / 2;
// If x is a perfect square
int sqr = mid * mid;
if (sqr == x)
return mid;
if (sqr <= x) {
start = mid + 1;
ans = mid;
} else {
end = mid - 1;
}
}
return ans;
}
public static void main(String[] args) {
// Test the function
System.out.println(floorSqrt(16)); // Output: 4
System.out.println(floorSqrt(17)); // Output: 4
}
}
def floorSqrt(x):
# Base cases
if x == 0 or x == 1:
return x
start, end = 1, x // 2
ans = None
# Do Binary Search for floor(sqrt(x))
while start <= end:
mid = (start + end) // 2
# If x is a perfect square
sqr = mid * mid
if sqr == x:
return mid
if sqr <= x:
start = mid + 1
ans = mid
else:
end = mid - 1
return ans
# Test the function
print(floorSqrt(16)) # Output: 4
print(floorSqrt(17)) # Output: 4
function floorSqrt(x) {
// Base cases
if (x === 0 || x === 1)
return x;
let start = 1, end = Math.floor(x / 2), ans;
// Do Binary Search for floor(sqrt(x))
while (start <= end) {
let mid = Math.floor((start + end) / 2);
// If x is a perfect square
let sqr = mid * mid;
if (sqr === x)
return mid;
if (sqr <= x) {
start = mid + 1;
ans = mid;
} else {
end = mid - 1;
}
}
return ans;
}
// Test the function
console.log(floorSqrt(16)); // Output: 4
console.log(floorSqrt(17)); // Output: 4
Output
4 4
Maths for Data Structure and Algorithms (DSA) | A Complete Guide
Maths is a fundamental component of learning Data Structure and Algorithms, just like in programming. Maths is primarily used to evaluate the effectiveness of different algorithms. However, there are situations when the answer requires some mathematical understanding or the problem has mathematical characteristics and certain problems demand more than just code. They require a mathematical perspective and a recognition of patterns and characteristics that go beyond the syntax of programming languages. Therefore, understanding maths is essential to know data structures and algorithms. So here in this Maths Guide for Data Structure and Algorithms (DSA), we will be looking into some commonly used concepts of Maths in DSA.
Table of Content
- GCD and HCF (Euclidean Algorithm)
- Divisors of a number
- Prime numbers using Sieve of Eratosthenes
- Square root
- Modular Arithmetic
- Fast Power-Exponentiation by Squaring
- Factorial of a number
- Fibonacci Number
- Catalan Numbers
- Euler Totient Function
- Prime numbers & Primality Tests
- Prime Factorization & Divisors
- Chinese Remainder Theorem
- Practice Problems based on Maths for DSA
- Most Frequently Asked Questions (FAQs)