# Nth root of M

Posted in  Vinay Khatri
Last updated on December 9, 2022

## Problem

Given two integers m and n, find the value of n?m.

#### Sample Input

`2?9`

`3`

3*3 = 9

## Approach

We can use Newton Raphson's method to solve this problem since it's a real-valued function. In this method, we start from a random guess and iteratively approach the result.

Following is the equation for the Newton Raphson method:

x(K+1) = x(K) – f(x) / f’(x),

where f(x) = x^(N) – A so f’(x) = N*x^(N - 1) and x(K) denoted the value of x at Kth iteration putting the values and simplifying, x(K + 1) = (1 / N) * ((N - 1) * x(K) + A / x(K) ^ (N - 1)).

According to the above relation, we keep iterating the value of x until the difference between two consecutive values is the lowest possible.

### Complexity Analysis

The time complexity is O(N* log(M)), and the space complexity is O(1)

#### C++ Programming

```#include <bits/stdc++.h>
using namespace std;

double solve(int M, int N)
{
// initially guessing a random number
double prevX = rand() % 10;

double acc = 1e-3;

// initializing difference between two roots
double diff = INT_MAX;

// currX denotes current value of x
double currX;

// iterate until we reach desired accuracy
while (diff > acc)
{
// calculating current value from previous
// value
currX = ((N - 1.0) * prevX +
(double)M/pow(prevX, N-1)) / (double)N;

diff = abs(currX - prevX);
prevX = currX;
}

return currX;
}

int main()
{
int N = 2;
int M = 9;

double ans = solve(M, N);
cout << "Root is " << ans << endl;

return 0;
}```

#### Output

`Root is 3`

#### Java Programming

```class Solution
{
static double solve(int M, int N)
{
// initially guessing a random number
double prevX = Math.random() % 10;

double acc = 0.001;

double diff = 2147483647;

// currX denotes current value of x
double currX = 0.0;

// loop until we reach desired accuracy
while (diff > acc)
{
// calculating current value from previous
// value
currX = ((N - 1.0) * prevX +
(double)M / Math.pow(prevX, N - 1)) / (double)N;
diff = Math.abs(currX - prevX);
prevX = currX;
}
return currX;
}

public static void main (String[] args)
{
int N = 2;
int M = 9;

double ans = solve(M, N);
System.out.println("Root is " + Math.round(ans*1000.0)/1000.0);
}
}```

#### Output

```Root is 3.0
```

#### Python Programming

```import math
import random

def solve(M,N):
# initially guessing a random number
prevX = random.randint(1,101) % 10

acc = 0.001

diff = 2147483647

currX=0.0

# iterate until we reach desired accuracy
while (diff > acc):
# calculating current value from previous value
currX = ((N - 1.0) * prevX +
M/pow(prevX, N-1)) /N

diff = abs(currX - prevX)
prevX = currX;

return currX

N = 2
M = 9

ans = solve(M, N)

print("Root is ", ans)```

#### Output

`Root is  3.0`