Find Nth Root Of M

Easy
0/40
Average time to solve is 10m
profile
Contributed by
526 upvotes
Asked in companies
DirectiAmazon

Problem statement

You are given two positive integers 'n' and 'm'. You have to return the 'nth' root of 'm', i.e. 'm(1/n)'. If the 'nth root is not an integer, return -1.


Note: 
'nth' root of an integer 'm' is a number, which, when raised to the power 'n', gives 'm' as a result.


Example: 
Input: ‘n’ = 3, ‘m’ = 27

Output: 3

Explanation: 
3rd Root of 27 is 3, as (3)^3 equals 27.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input consists of two space-separated integers, n and m.


Output Format: 
Return an integer that denotes the nth root of m in a separate line. If such an integer doesn't exist return -1.


Note: 
You don't have to print anything. It has already been taken care of. Just Implement the given function.
Sample Input 1:
3 27


Sample Output 1:
3


Explanation For Sample Input 1:
3rd Root of 27 is 3, as (3)^3 equals 27.


Sample Input 2:
4 69


Sample Output 2:
-1


Explanation For Sample Input 2:
4th Root of 69 is not an integer, hence -1.


Expected Time Complexity:
Try to do this in O(log(n+m)).


Constraints:
1 <= n <= 30
1 <= m <= 10^9

Time Limit: 1 sec.
Hint

Is there any monotonic function followed for this problem?

Approaches (2)
Binary Search

The idea for this approach is to use binary search to find an integer equal to ‘M’ when multiplied by itself ‘N’ times.

 

The exponential function is an increasing function (i.e., monotonic), and thus, using binary search, we will try out different possible square roots; let’s suppose we are currently on ‘X’, then we will find 

  1. If ‘XN’ is greater than ‘M’, then we must reduce the higher bound of our search space.
  2. If ‘XN’ is less than ‘M’, then we must increase the lower bound of our search space.
  3. If ‘XN’ equals ‘M’, we found our ‘N’th root.
     

To find the value of ‘XN’, we can use a loop, which will iterate ‘N’ times.

 

The steps are as follows:-

// Function to find the Nth root of M

function NthRoot(int n, int m):

  1. Declare a variable ‘ans’, which is initially assigned to ‘-1’.
  2. Declare two more variables, ‘s’ and ‘e’, initially assigned to ‘1’ and ‘m’, respectively.
  3. While ‘s <= e’:
    • Declare a variable ‘mid’ and assign it to ‘(s + e) / 2’.
    • Declare a variable ‘x’ and assign it to ‘1’.
    • Iterate from index ‘1’ to ‘n’:
      • Assign ‘x’ to ‘x * mid’.
      • If ‘x > m’:
        • Break the loop.
    • If ‘x == m’:
      • Assign ‘ans' to ‘mid’.
      • Break the loop.
    • If ‘x > m’:
      • Assign ‘e’ to ‘mid - 1’.
    • else:
      • Assign ‘s’ to ‘mid + 1'.
  4. Return ‘ans'.
Time Complexity

O( n * log(M) ), Where ‘N’ and ‘M’ are input integers.

In the above algorithm, the search space is ‘M’, and hence in ‘log(M)’ iterations, we will find the ‘N’th root, and in each iteration, we find the ‘N’th power of ‘mid’ using a loop.

Hence the time complexity will be O( n * log(M) )

Space Complexity

O( 1 ).
 

In the above algorithm, we only use variables.

 

Hence the space complexity will be O( 1 ).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Find Nth Root Of M
Full screen
Console