# Why TLE? Java O(10^6) or O(n^(1/3)) solution. Less than 100ms for TLE case.

• The idea is to search from 2 to n^(1/3), and check if there is an answer with 4 ones or more. Then check if there are 3 ones by solving an equation. Because it is simple equation, we can use binary search. And at last, if cannot find, n - 1 is the answer.

I got timeout every time on different test cases:
"541064907662839644"
"916365355264637559"

But when I run the code by inputing it as custom test cases. All TLE cases can finish within 100ms. What is wrong?

``````public class Solution {
public String smallestGoodBase(String n) {
long num = Long.valueOf(n);
for (int i = 2; i < num / i / i; ++i) {
if (check(num, i)) {
return "" + i;
}
}
long p = solveEquation(num);
if (p > 0) {
return "" + p;
} else {
return "" + (num - 1);
}
}

// solve equation:
// x^2 + x + 1 = n, return x if exists.
public long solveEquation(long n) {
long l = 2;
long r = (long)Math.sqrt((double)n);
while (l <= r) {
long mid = (l - r) / 2 + r;
long left = mid * mid;
long right = n - 1 - mid;
if (left == right) {
return mid;
} else if (left > right) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1;
}

// Check if the base is the answer.
public boolean check(long n, long base) {
long k = 1;
while (k < n) {
if (base >= (Long.MAX_VALUE - 1) / k) {
break;
}
k = base * k + 1;
}
return k == n;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.