BS-11. Find the Nth Root of an Integer

1. Problem Statement & Overview

Given two integers $n$ and $m$, our objective is to find the $n$-th root of $m$. The $n$-th root of an integer $m$ is a number $x$ such that multiplying $x$ by itself $n$ times yields $m$ ($x^n = m$).

• Example 1: If $n = 3$ and $m = 27$, the 3rd root of 27 is $3$ because $3 \times 3 \times 3 = 27$.
• Example 2: If $n = 4$ and $m = 69$, there is no integer whose 4th power equals 69 ($1^4=1$, $2^4=16$, $3^4=81$). In such cases where an exact integer root does not exist, the program must return $-1$.

2. Naive Approach: Linear Search

The most intuitive way to solve this is to test integers sequentially starting from $1$ up to $m$.

How It Works

1. Run a loop variable $i$ from $1$ to $m$.
2. Compute $i^n$ (using either a simple multiplication loop or binary exponentiation).
3. If $i^n == m$, return $i$.
4. If $i^n > m$, it means we have crossed the target value. Since further increments will only make the product larger, we can immediately break out of the loop and return $-1$.

Naive Code Structure

int linearSearchNthRoot(int n, int m) {
    for (int i = 1; i <= m; i++) {
        long long val = computePower(i, n);
        if (val == m) return i;
        if (val > m) break; // Exceeded target, no exact root exists
    }
    return -1;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(m \times \log n)$ if using binary exponentiation to calculate $i^n$, or $\mathcal{O}(m \times n)$ if using a simple loop for exponentiation. In the worst case, the algorithm iterates up to $m$.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space.

3. Core Mental Model: Why Binary Search on Answers?

The linear search approach is too slow when $m$ is large (e.g., $10^9$). We need a faster way to eliminate large blocks of candidate integers.

Real-Life Analogy: The Price Guessing Game

Imagine playing a game where you must guess a hidden target number between $1$ and $100$. If you guess $50$ and the host says "Too high," you instantly discard $50$ and everything above it, cutting your search space in half.

This exact monotonic property applies to finding the $n$-th root:

• If our current candidate mid raised to the power $n$ ($\text{mid}^n$) is less than $m$, our answer must lie to the right (we need a larger number).
• If $\text{mid}^n$ is greater than $m$, our answer and anything larger can never be valid. We must discard the right half and move to the left.

4. Step-by-Step Evolution: Binary Search on Answers

By recognizing that the search space $[1, m]$ is strictly sorted and monotonic, we can apply Binary Search.

Algorithmic Steps

1. Define the Search Space: Set $\text{low} = 1$ and $\text{high} = m$.
2. Find the Midpoint: $\text{mid} = \text{low} + (\text{high} - \text{low}) / 2$.
3. Evaluate $\text{mid}^n$: Compare the computed power against $m$.
   • If $\text{mid}^n == m$, we found our exact root; return $\text{mid}$.
   • If $\text{mid}^n < m$, the root must be larger; shift $\text{low} = \text{mid} + 1$.
   • If $\text{mid}^n > m$, the root must be smaller; shift $\text{high} = \text{mid} - 1$.
4. Termination: If $\text{low}$ crosses $\text{high}$ without finding an exact match, return $-1$.

5. Walkthrough 1: Successful Search ($n = 3, m = 27$)

Let's trace the algorithm step-by-step for finding the 3rd root of 27:

• Initial Range: $\text{low} = 1$, $\text{high} = 27$

Iteration 1:
   - mid = (1 + 27) / 2 = 14
   - 14^3 = 2744 (Greater than 27)
   - Action: Eliminate everything >= 14. High moves to 13.
   
Iteration 2:
   - low = 1, high = 13
   - mid = (1 + 13) / 2 = 7
   - 7^3 = 343 (Greater than 27)
   - Action: Eliminate everything >= 7. High moves to 6.

Iteration 3:
   - low = 1, high = 6
   - mid = (1 + 6) / 2 = 3 (integer division)
   - 3^3 = 27 (Equal to 27!)
   - Action: Return 3 as the exact Nth root.

6. Walkthrough 2: Unsuccessful Search ($n = 4, m = 69$)

Let's trace an example where no integer root exists (4th root of 69):

• Initial Range: $\text{low} = 1$, $\text{high} = 69$

7. Real-World Practical Pitfalls: Integer Overflow

When computing $\text{mid}^n$ for large constraints (e.g., finding the 10th root of $10^9$), standard integer types will overflow.

The Overflow Problem

If $m = 10^9$ and $n = 10$, $\text{mid}$ can be around $10^9 / 2 = 5 \times 10^8$. Raising $5 \times 10^8$ to the 10th power produces a number near $10^{90}$, which far exceeds 64-bit integer limits (long long in C++).

The Solution: Controlled Multiplication with Early Exit

Instead of computing $\text{mid}^n$ fully in one go and risking an overflow, we compute it iteratively while multiplying. The moment our accumulated product exceeds $m$, we abort early and return a flag indicating that the value is too large.

// Returns: 2 if (mid^n > m), 1 if (mid^n == m), 0 if (mid^n < m)
int func(long long mid, int n, int m) {
    long long ans = 1;
    for (int i = 1; i <= n; i++) {
        ans = ans * mid;
        if (ans > m) return 2; // Early exit to prevent overflow
    }
    if (ans == m) return 1;
    return 0;
}

8. Complete Optimized Implementation

Below is the robust, production-ready solution implementing Binary Search on Answers with overflow prevention:

class Solution {
private:
    // Helper function to calculate mid^n with overflow protection
    int powerCheck(long long mid, int n, int m) {
        long long ans = 1;
        for (int i = 1; i <= n; i++) {
            ans = ans * mid;
            if (ans > m) return 2; // Exceeds m
        }
        if (ans == m) return 1;    // Exactly equals m
        return 0;                  // Less than m
    }

public:
    int NthRoot(int n, int m) {
        long long low = 1, high = m;
        
        while (low <= high) {
            long long mid = low + (high - low) / 2;
            int res = powerCheck(mid, n, m);
            
            if (res == 1) {
                return mid; // Exact root found
            } else if (res == 2) {
                high = mid - 1; // Mid^n is too large, move left
            } else {
                low = mid + 1;  // Mid^n is too small, move right
            }
        }
        
        return -1; // No integer nth root exists
    }
};

9. Summary and Key Takeaways

• Problem Recognition: When asked to find a specific boundary value or root within a known range $[1, m]$, Binary Search on Answers is the optimal strategy.
• Search Space Definition: Always initialize $\text{low} = 1$ and $\text{high} = m$ to cover all potential integer solutions.
• Monotonic Elimination: If $\text{mid}^n > m$, discard the right half ($\text{high} = \text{mid} - 1$); if $\text{mid}^n < m$, discard the left half ($\text{low} = \text{mid} + 1$).
• Efficiency: Reduces time complexity from linear $\mathcal{O}(m)$ to logarithmic $\mathcal{O}(\log m \times n)$, making it capable of handling extremely large inputs efficiently.
• Production Safety: Always watch out for integer overflow when computing powers; use iterative multiplication with an early exit threshold (> m) rather than native exponentiation functions.