shreyansh

Find the nth Root

Understanding the Problem:

  • We need to find an integer kk such that k$$^n ≤ xx and (k+1)$$^n > xx.
  • 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 11 to x/2x/2.
  • Mid Calculation: Compute the middle point to divide the range.
  • Comparison:
    • If mid$$^n = xx, we’ve found the exact nnth root.
    • If mid$$^n < xx , the possible root is in the upper half (move the lower bound up).
    • If mid$$^n > xx, 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 ≤ xx.
  • 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
    }
}