Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 29, 2018 03:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/5e8381d98c8ea7782b3506a60e4a947d to your computer and use it in GitHub Desktop.
Save jianminchen/5e8381d98c8ea7782b3506a60e4a947d to your computer and use it in GitHub Desktop.
root of a number - look into test cases - fail two cases
import java.io.*;
import java.util.*;
class Solution {
/*
input: x = 7, n = 3
output: 1.913
1,2,3
(1,2)
0.001
if x = 7, what is n? logn ->
0, 0.0001,
0 - 1, 1000,
0 - 7 , 7000 -> x = 7, log1000x = 10logx = 10 log7 = 30
what is n?
0 -> upper bound, x > 1, x,
x < 1, 1
[0, max(x, 1)] - range
input: x = 9, n = 2
output: 3
1,2,3...
1,4,9
*/
static double root(double x, int n) {
// your code goes here
int s = 0;
int e = Math.max(1*1000, (int)x*1000);
int m = 0;
double sample = 0.0;
double result = 0.0;
while (s <= e) {
m = s + (e-s)/2;
sample = test((double)m/1000.0, n);
double diff = Math.abs(sample - x); // 0.001 -> 0.0008 -> 0.001, 0.0012 -> 0.001 diff <= 0.0005
if (diff <= 0.0005) {
result = (double)m/1000;
break;
}
else if (sample < x)
{
s = m + 1;
}
else {
e = m - 1;
}
}
return result;
}
static double test(double x, int n){
double t = x;
while (n > 1) {
t *= x;
n--;
}
return t;
}
public static void main(String[] args) {
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment