Find nth Root of m | GeeksforGeeks Solution Explained | Binary Search

The “Find nth Root of m” problem is a classic example of how brute force and binary search can be used to solve mathematical problems efficiently. In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

Here’s the [Problem Link] to begin with.

What Does the Problem Say?

Given two positive integers n and m, your task is to find the nth root of m, i.e., find an integer x such that x^n = m.
If no such integer exists, return -1.

Example 1

Input:
n = 3, m = 27

Output:
3

Explanation:
3^3 = 27, so the answer is 3.

Example 2

Input:
n = 4, m = 69

Output:
-1

Explanation:
There is no integer x such that x^4 = 69.

Brute Force Solution (Linear Scan)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Try Every Number:
   Start from 1 and go up to m. For each number, check if its nth power equals m.
2. Return the Answer:
   If you find such a number, return it. If you reach the end, return -1.
3. Why does this work?
   We check every possible integer, so we’re sure to find the answer if it exists.

This approach is easy to understand but not very efficient for large values of m.

Code Implementation

class Solution:
    def nthRoot(self, n: int, m: int) -> int:
        for i in range(1, m + 1):
            if i**n == m:         # Check if i^n equals m
                return i          # Return i if it matches
        return -1                 # Return -1 if no such integer found

Code Explanation

• Start from 1 and check every number up to m.
• If i**n equals m, return i.
• If no such number is found, return -1.

Dry Run

Input:
n = 3, m = 27

• i = 1: 1^3 = 1 ≠ 27
• i = 2: 2^3 = 8 ≠ 27
• i = 3: 3^3 = 27 → found! Return 3

Final Output:
3

Time and Space Complexity

• Time Complexity: O(m)
  We may have to check every number up to m.
• Space Complexity: O(1)
  Only a variable for looping.

Conclusion

The brute force approach is simple and works for small values of m, but it’s too slow for large inputs.

Optimal Solution (Binary Search)

Intuition and Approach

We can do much better using binary search:

1. Binary Search Range:
   The answer lies between 1 and m. Use binary search to find the integer whose nth power equals m.
2. Check the Middle Value:
   • If mid^n equals m, return mid.
   • If mid^n is less than m, search in the higher half.
   • If mid^n is greater than m, search in the lower half.
3. Why does this work?
   Binary search efficiently narrows down the possible values, making it much faster for large m.

Code Implementation

class Solution:
    def nthRoot(self, n: int, m: int) -> int:
        low = 1
        high = m
        while low <= high:
            mid = (low + high) // 2
            if mid**n == m:            # Check if mid^n equals m
                return mid             # Return mid if it matches
            elif mid**n < m:           # If mid^n is less, search higher
                low = mid + 1
            else:                      # If mid^n is more, search lower
                high = mid - 1
        return -1                      # Return -1 if no integer root found

Code Explanation

• Use binary search between 1 and m.
• If mid**n equals m, return mid.
• If mid**n is less than m, move low up.
• If mid**n is greater than m, move high down.
• If no such number is found, return -1.

Dry Run

Input:
n = 3, m = 27

• low = 1, high = 27
• mid = 14, 14^3 = 2744 > 27 → high = 13
• mid = 7, 7^3 = 343 > 27 → high = 6
• mid = 3, 3^3 = 27 → found! Return 3

Final Output:
3

Time and Space Complexity

• Time Complexity: O(log m)
  Binary search divides the range each time.
• Space Complexity: O(1)
  Only a few pointers.

Conclusion

The binary search solution is efficient and works well for large values of m. It’s the best approach for interviews and practical use.

Final Thoughts

The “Find nth Root of m” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.