Find Nth Root Of M

The idea for this approach is to use binary search to find an integer equal to ‘M’ when multiplied by itself ‘N’ times.

The exponential function is an increasing function (i.e., monotonic), and thus, using binary search, we will try out different possible square roots; let’s suppose we are currently on ‘X’, then we will find 

1. If ‘X^N’ is greater than ‘M’, then we must reduce the higher bound of our search space.
2. If ‘X^N’ is less than ‘M’, then we must increase the lower bound of our search space.
3. If ‘X^N’ equals ‘M’, we found our ‘N’th root.
    

To find the value of ‘X^N’, we can use a loop, which will iterate ‘N’ times.

The steps are as follows:-

// Function to find the Nth root of M

function NthRoot(int n, int m):

1. Declare a variable ‘ans’, which is initially assigned to ‘-1’.
2. Declare two more variables, ‘s’ and ‘e’, initially assigned to ‘1’ and ‘m’, respectively.
3. While ‘s <= e’:
   • Declare a variable ‘mid’ and assign it to ‘(s + e) / 2’.
   • Declare a variable ‘x’ and assign it to ‘1’.
   • Iterate from index ‘1’ to ‘n’:
     • Assign ‘x’ to ‘x * mid’.
     • If ‘x > m’:
       • Break the loop.
   • If ‘x == m’:
     • Assign ‘ans' to ‘mid’.
     • Break the loop.
   • If ‘x > m’:
     • Assign ‘e’ to ‘mid - 1’.
   • else:
     • Assign ‘s’ to ‘mid + 1'.
4. Return ‘ans'.

• Let’s say X is the Nth root of M.
  • X = M^{(1 / N)}
• The above equation can be written as follows:
  • X^N = M
  • X^N - M = 0
  • Let’s assume F(X) = X^N - M
• Now we need to find the root of this equation, for which we can use the Newton Raphson method to solve this equation.
• In Newton's Raphson method we start with an initial guess value of X (any random initial value is fine) and iterate through a process that takes us towards the actual solution of the equation.
  • Let’s say X(0) is the initial guess value.
  • The relationship between the current value of solution value x(k) and the solution of the equation in the next iteration X(K + 1) is as follows:
    • X(K + 1) = X(K) - F(X(K)) / F'(X(K)), where F'(X(K)) denotes the value derivative of F(X) at X = X(K).                                    ....(1)
  • In the given case F'(X(k)) = N * X(K)^N - 1.
  • So equation (1) can be written as follows:
    • X(K + 1) = X(K) - (X(K)^N - M) / (N * X(K)^N - 1)
    • X(K + 1) = (X(K) * (N * X(K)^N - 1) - X(K)^N + M) / (N * X(K)^N - 1))
    • X(K + 1) = (X(K)^N * (N - 1) + M) / (N * X(K)^N - 1)
• So using the above formula to calculate the new possible solution value X. Till the gap between X(K + 1) and X(K) becomes less than 10-2.
• Then we will extract the integer value of X and store it in the variable ‘integerAns’.
• Then, we will check whether ‘integerAns’ is the correct Nth Root of M. If not, we will assign ‘-1’ to ‘integerAns’.
• At last, we get our required solution.