Fifth root of a number - GeeksforGeeks
Given a number, print floor of 5'th root of the number.
The idea is to do Binary Search. We start from n/2 and if its 5’th power is more than n, we recur for interval from n/2+1 to n. Else if power is less, we recur for interval 0 to n/2-1
A simple solution is initialize result as 0, keep incrementing result while result5 is smaller than or equal to n. Finally return result – 1.
Time complexity of above solution is O(n1/5)
Given a number, print floor of 5'th root of the number.
Input : n = 250 Output : 3 Fifth square root of 250 is between 3 and 4 So floor value is 3.
The idea is to do Binary Search. We start from n/2 and if its 5’th power is more than n, we recur for interval from n/2+1 to n. Else if power is less, we recur for interval 0 to n/2-1
// Returns floor of 5'th root of nint floorRoot5(int n){ // Base cases if (n == 0 || n == 1) return n; // Do Binary Search for floor of 5th square root int low = 1, high = n, ans = 0; while (low <= high) { // Find the middle point and its power 5 int mid = (low + high) / 2; long int mid5 = mid*mid*mid*mid*mid; // If mid is the required root if (mid5 == n) return mid; // Since we need floor, we update answer when // mid5 is smaller than n, and move closer to // 5'th root if (mid5 < n) { low = mid + 1; ans = mid; } else // If mid^5 is greater than n high = mid - 1; } return ans;}A simple solution is initialize result as 0, keep incrementing result while result5 is smaller than or equal to n. Finally return result – 1.
// Returns floor of 5th root of nint floorRoot5(int n){ // Base cases if (n == 0 || n == 1) return n; // Initialize result int res = 0; // Keep incrementing res while res^5 is // smaller than or equal to n while (res*res*res*res*res <= n) res++; // Return floor of 5'th root return res-1;}
Time complexity of above solution is O(Log n)
We can also use Newton Raphson Method to find exact root. See this for implementation.
Source : http://qa.geeksforgeeks.org/7487/program-calculate-fifth-without-using-mathematical-operators
Read full article from Fifth root of a number - GeeksforGeeks