Nth root of M

Posted in

Nth root of M
vinaykhatri

Vinay Khatri
Last updated on February 21, 2024

    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:

    Leave a Comment on this Post

    0 Comments