The “Find nth Root of m” problem is a classic example of how brute force and binary search can be used to solve mathematical problems efficiently. In this blog, we\u2019ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n Given two positive integers Input:<\/strong> Output:<\/strong> Explanation:<\/strong> Input:<\/strong> Output:<\/strong> Explanation:<\/strong> Let\u2019s solve the problem in the most straightforward way:<\/p>\n\n\n\n This approach is easy to understand but not very efficient for large values of m.<\/p>\n\n\n\nWhat Does the Problem Say?<\/h2>\n\n\n\n
n<\/code> and m<\/code>, your task is to find the nth root of m<\/strong>, i.e., find an integer x<\/code> such that x^n = m<\/code>.
If no such integer exists, return -1<\/code>.<\/p>\n\n\n\nExample 1<\/h3>\n\n\n\n
n = 3, m = 27<\/code><\/p>\n\n\n\n3<\/code><\/p>\n\n\n\n
3^3 = 27, so the answer is 3.<\/p>\n\n\n\nExample 2<\/h3>\n\n\n\n
n = 4, m = 69<\/code><\/p>\n\n\n\n-1<\/code><\/p>\n\n\n\n
There is no integer x such that x^4 = 69.<\/p>\n\n\n\n
\n\n\n\nBrute Force Solution (Linear Scan)<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
Start from 1 and go up to m. For each number, check if its nth power equals m.<\/li>\n\n\n\n
If you find such a number, return it. If you reach the end, return -1.<\/li>\n\n\n\n
We check every possible integer, so we\u2019re sure to find the answer if it exists.<\/li>\n<\/ol>\n\n\n\nCode Implementation<\/h3>\n\n\n\n