##
**
Problem
**

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

####
**
***
Sample
*
Input

*Sample*Input

2?9

####
**
Sample Output
**

3

####
**
Explanation
**

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 numberdouble prevX = rand() % 10; double acc = 1e-3;// initializing difference between two rootsdouble diff = INT_MAX;// currX denotes current value of xdouble currX;// iterate until we reach desired accuracywhile (diff > acc) {// calculating current value from previous// valuecurrX = ((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 numberdouble prevX = Math.random() % 10; double acc = 0.001; double diff = 2147483647;// currX denotes current value of xdouble currX = 0.0;// loop until we reach desired accuracywhile (diff > acc) {// calculating current value from previous// valuecurrX = ((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

**
People are also reading:
**

## Leave a Comment on this Post