Find the nth Root

Understanding the Problem:

• We need to find an integer $k$ such that k$$^n ≤ $x$ and (k+1)$$^n > $x$.
• This is analogous to finding a point in a sorted array where the value at the point is closest to but not exceeding a given target.

Algorithm Steps:

• Initialization: Start with the full range of potential roots from $1$ to $x/2$.
• Mid Calculation: Compute the middle point to divide the range.
• Comparison:
  • If mid$$^n = $x$, we’ve found the exact $n$^th root.
  • If mid$$^n < $x$ , the possible root is in the upper half (move the lower bound up).
  • If mid$$^n > $x$, the possible root is in the lower half (move the upper bound down).
• Update Result: Track the largest value of midmid that satisfies mid$$^n ≤ $x$.
• Termination: When the search space is exhausted, return the largest integer found that satisfies the condition.

class Solution {
    public int myNthRoot(int x, int n) {
        // Handle edge cases for 0 and 1
        if (x == 0 || x == 1) {
            return x; 
        }
 
        // Initialize binary search range
        int start = 1;
        int end = x / 2;
        int result = 1;
 
        // Binary search loop
        while (start <= end) {
            int mid = start + (end - start) / 2;
            
            long product = 1;
            for (int i = 0; i < n; i++) {
                product *= mid;
                if (product > x) break; // Early exit if product exceeds x
            }
 
            // Check the product against x
            if (product == x) {
                return mid; // Found exact nth root
            } else if (product < x) {
                result = mid; // Update result as mid might be the answer
                start = mid + 1; // Move to the right half
            } else {
                end = mid - 1; // Move to the left half
            }
        }
 
        // Return the largest integer such that result^n <= x
        return result;
    }
 
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.myNthRoot(16, 4)); // Output: 2
        System.out.println(sol.myNthRoot(27, 3)); // Output: 3
        System.out.println(sol.myNthRoot(64, 3)); // Output: 4
        System.out.println(sol.myNthRoot(10, 2)); // Output: 3
    }
}