Problem
Given two integers m and n, find the value of n?m.
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 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
People are also reading:
