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


  • 0
    S

    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;
        }
    }
    

Log in to reply
 

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