Nth root of M

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:

• Merge Two Sorted Arrays in-place
• Print a given matrix in spiral form
• Print all subarrays with 0 sum
• Maximum of all Subarrays of size K
• Program to Rotate an Array
• Longest subarray with sum as K
• Rod Cutting Problem
• Dutch National Flag Problem
• Subarray with Sum k
• Create a mirror of an m–ary Tree