Find Nth Root Of M¶
Intuition¶
We know that raising a number to a power grows steadily (monotonically). This makes it perfect for binary search. Instead of checking every number, we can narrow down the possible root quickly using this method.
Complexity¶
| Space Complexity | Time Complexity |
|---|---|
| $\(\text{O}(1)\)$ | $\(\text{O}(\log{N})\)$ |
Code¶
public static int NthRoot(int n, int m) {
int left = 1, right = m, possibleRoot = 1;
// Binary search to find potential nth root
while (left <= right) {
int mid = left + (right - left) / 2;
long powerResult = mid;
for (int i = 1; i < n; ++i) {
powerResult *= mid;
}
if (powerResult <= m) {
// mid is a possible root; try to find a larger one
possibleRoot = mid;
left = mid + 1;
} else {
// mid^n is too large
right = mid - 1;
}
}
// Verify if the found root actually satisfies the condition
long finalCheck = possibleRoot;
for (int i = 1; i < n; ++i) {
finalCheck *= possibleRoot;
}
return finalCheck == m ? possibleRoot : -1;
}