Find Nth Root Of M in Java
In the following article, we are given two numbers, n, and m, where n represents the degree of the root and m is the number whose root we need to find. The problem is to find the integer value of the nth root of m. If no integer value exists for the nth root, the function should return -1.The nth root of a number offers precision, accuracy, and applications in engineering, science, finance, cryptography, and mathematical curiosity. It's used in public-key encryption algorithms like RSA and can be intellectually stimulating, allowing exploration of mathematical concepts.
Example1:
Input: n = 3, m = 27
Output: 3
Explanation: The cube root of 27 is 3 because 3^3=27
Example2:
Input: n = 2, m = 81
Output: 9
Explanation: The square root of 81 is 9 because 9^2=81
Using Naive Approach
Algorithm
Step 1: Initialize a loop iterating from 1 to m.
Step 2: Increase the current loop variable to the power of n each iteration.
Step3: Compare power calculation result with m, return current loop variable if equal.
Step 4: Continue to the next iteration if no match is found.
Step 5: Return -1 if the loop completes without finding a match.
Step 6: Call the algorithm with test cases and print results.
Here is an explanation of finding the nth root of m using a naive approach:
FileName:NthRoot.java
public class NthRoot {
public static int nthRootNaive(int n, int m) {
for (int i = 1; i <= m; i++) {
// If i raised to the power of n equals m, return i
if (Math.pow(i, n) == m) {
return i;
}
}
// If no n-th root is found, return -1
return -1;
}
public static void main(String[] args) {
int n = 3, m = 27;
System.out.println(nthRootNaive(n, m));
}
}
Output:
3
Complexity analysis: The above approach's time complexity is O(m), where the loop runs from 1 to m in the worst case, and the space complexity is O(1), where the algorithm uses a constant amount of extra space.
Using Optimized Approach
Algorithm
Step 1: Return 0 if the input number is 0.
Step 2: Set the lower bound to 1 and the upper bound to m.
Step 3: Loop while the lower bound is less than or equal to the upper bound.
Step 4: Calculate the midpoint to avoid overflow.
Step 5: Return midpoint as root if raised to the power of n equals m.
Step 6: If the power calculation result is less than m, adjust the lower bound to narrow the search.
Step 7: If the power calculation result is greater than m, adjust the upper bound to narrow the search.
Step 8: Return -1 if no match is found after loop.
Step 9: Call the algorithm with test cases and print results.
Here is an explanation of finding the nth root of m using an optimized approach:
FileName:NthRoot1.java
public class NthRoot1 {
public static int nthRootOptimized(int n, int m) {
// Special case: if m is 0, the n-th root of 0 is 0
if (m == 0) {
return 0;
}
// Initialize the low and high bounds for binary search
int low = 1;
int high = m;
// Perform binary search
while (low <= high) {
// Calculate the mid-point to avoid overflow
int mid = low + (high - low) / 2;
// Calculate mid raised to the power of n
long midPow = (long) Math.pow(mid, n);
// Check if midPow is equal to m
if (midPow == m) {
return mid; // n-th root found
} else if (midPow < m) {
low = mid + 1; // Search in the higher half
} else {
high = mid - 1; // Search in the lower half
}
}
// If no n-th root is found, return -1
return -1;
}
public static void main(String[] args) {
int n = 3, m = 27;
System.out.println(nthRootOptimized(n, m));
}
}
Output:
3
Complexity analysis: The time complexity of the above approach is O(log m). The binary search reduces the search space logarithmically, and the space complexity is O(1). The algorithm uses a constant amount of extra space.