Day 11 Binary Search | Striver 180 | takeUforward
Post
Cancel

# Day 11 Binary Search | Striver 180 | takeUforward

## Problem 1: Nth Root Of M

You are given two positive integers N and M. You have to find the Nth root of M i.e. M^(1/N).

### Worst

Import math library and use built-in methods.

### Better

Apply binary search.

Time Complexity: $O(nlog(m(d^10)))$

Auxiliary Space: $O(1)$

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include using namespace std; class Solution { public: int multiply(int number, int times, int mx) { long long int product = 1; for (int i = 0; i < times; i++) { product *= number; if (product > mx) return mx + 2; } return product; } int NthRoot(int n, long long m) { int l = 1; int r = m; while (l <= r) { int mid = l + (r - l) / 2; int d = multiply(mid, n, m); if (d == m) return mid; if (d < m) { l = mid + 1; } else { r = mid - 1; } } return -1; } }; // { Driver Code Starts. int main() { int tc; cin >> tc; while (tc--) { int n, m; cin >> n >> m; Solution ob; int ans = ob.NthRoot(n, m); cout << ans << "\n"; } return 0; } // } Driver Code Ends

### Optimal

Time Complexity: $O(log(M) * log(N))$

Auxiliary Space: $O(1)$

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 double findNthRootOfM(int n, long long m) { double error = 1e-7; double diff = 1e18; double xk = 2; while (diff > error) { double xk_1 = (pow(xk, n) * (n - 1) + m) / (n * pow(xk, n - 1)); diff = abs(xk - xk_1); xk = xk_1; } return xk; }