Created
May 31, 2017 19:39
-
-
Save jianminchen/5f296becfac20c0e9b1d4a1190275e5d to your computer and use it in GitHub Desktop.
Root of a number - error range is 0.001 - practice code, fixed the grammar errors and ran a few test cases, edge cases as well.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Diagnostics; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace RootOfANumber | |
{ | |
/// <summary> | |
/// May 30, 2017 - code practice | |
/// x > 1, 7, 1 7 -> 1000 - 7000 o(logn) , 1000x - O(log1000x) = 10 logx | |
//space O(1) | |
// x^(1/n) | |
// 4^ (1/2) = 2 | |
// x = 7, n = 3, Math.Abs(1.913 * 1.913 * 1.97 - 7) < 0.001 | |
// x = 9, n = 2, 2.999 * 2.999 | |
// 0.001 -> 3 decimals | |
// x >= 1 , 0 - 1 , > 1 | |
// x = 1, 1.000 = 1, n >0 | |
// x = 0, 0 , | |
// (0, 1) x in (0, 1) => 1/x (1, upper bound ), 1/ x | |
// (1, upper bound ), 0.001, | |
// given x > 1, 1 - x -> binary search 1 + ( x - 1)/ 2, compare power of n middle x | |
// 0.001 | |
/// </summary> | |
class RootOfANumber | |
{ | |
static void Main(string[] args) | |
{ | |
var result = root(0.001, 3); | |
Debug.Assert(Math.Abs(result - 0.1) < 0.001); | |
var result2 = root(1000, 3); | |
Debug.Assert(Math.Abs(result2 - 10) < 0.001); | |
} | |
// test case: 0 | |
// 1 | |
// 0.001, n = 3, 0.1 | |
// 1000 , n = 3, 10 | |
// .. | |
static double root(double x, int n) | |
{ | |
const double errorRange = 0.001; | |
// your code goes here | |
if (x == 0 || x == 1 || x < errorRange || Math.Abs(x - 1) < errorRange) // 0, 1 | |
{ | |
return x; | |
} | |
bool isLessThanOne = x < 1; // 0.001 | |
if (isLessThanOne) | |
{ | |
var reverse = getReverse(x); // | |
var result = root(reverse, n); | |
return 1000 / result / 1000.0; // 0.1 | |
} | |
// binary search to find the value | |
return FindRootBinarySearch(x, n, 1, x); // 1000 | |
} | |
public static double FindRootBinarySearch(double search, int n, double start, double end) // 1. 1000 | |
{ | |
while (start < end && (end - start) > 0.001) // while, not if. Fix writing error after mocking | |
{ | |
double middle = start + (end - start) / 2; // 1 + 999/2 (middle keep to 3 decimal ) | |
bool equalToSearch = isEqual(middle, search, n); // | |
bool middleBigger = isBigger(middle, search, n); | |
if (equalToSearch) return middle; | |
if (middleBigger) | |
{ | |
end = middle; // ? "end = middle - 0.001" | |
} | |
else | |
{ | |
start = middle; // ? "start = middle - 0.001" | |
} | |
} | |
return start; | |
} | |
// 0 - equal | |
// 1 - bigger | |
// -1 - smaller | |
private static bool isEqual(double middle, double search, int n) | |
{ | |
return Math.Abs(Math.Pow(middle, n) - search) < 0.001; // out-of-range | |
} | |
private static bool isBigger(double middle, double search, int n) | |
{ | |
double power = Math.Pow(middle, n); | |
return Math.Abs(power - search) > 0.001 && power > search; | |
} | |
// assume that x is in (0, 1) | |
private static double getReverse(double x) | |
{ | |
int result = (int) (1000 / Math.Max(x, 0.001)); // decimal to 3, 0.001 1000 * 1000 = 10 ^6 | |
return result / 1000.0; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment