Java accepted answer, 11ms


  • 2
    J

    sum base r == 1111... means sum = 1+r+r^2+r^3+...+r^p
    I tried two different search.

    1. for r = 2-10, increase p until sum>= n
    2. for p=2,3,4..., calculate r = sum^(1/p). then try a few numbers around r to see if the sum fits the above equation. In fact, I only tried r and got accepted by OJ.
        public String smallestGoodBase(String n) {
            long nl = 0, cur = 1;
            for (int i=n.length()-1;i>=0;i--){
                nl+=(n.charAt(i)-'0')*cur;
                cur*=10;
            }
            for (long i=2;i<10;i++){
                long s = 0;
                cur = 1;
                for (int j=0;j<nl;j++){
                    s+=cur;
                    cur*=i;
                    if (s == nl) return Long.toString(i);
                    if (s > nl) break;
                }
            }
            long res = nl-1;
            for (int i=2;i<1000;i++){
            	int r = (int)Math.pow(nl,1.0/i);
            	if (r<5) break;
            	if (helper(r,i,nl)&&res>r)
            		res = r;
            }
            return Long.toString(res);
        }
        boolean helper(int r, int i, long nl){
        	long res = 0;
        	long cur = 1; 
        	for(int j=0;j<=i;j++){
        		res+=cur;
        		cur*=r;
        		if (cur>1000000000)
        			cur%=1000000000;
        	}
        	if (res%1000000000 == nl%1000000000) return true;
        	else return false;
        }
    

  • 0
    This post is deleted!

  • 0
    D
    1. how can we assume r is in range 2-10 ?
    2. what is the meaning of r= sum^(1/p) ?

  • 0
    Z

    @darren5
    He is not assume r is in range 2-10, he just try to test if base [2, 10) is the solution first for some reason, maybe the majority of the test case is within base 10? I don't know, but the description says 2-10 maybe a little misleading.

    sum^(1/p) just calculate the nth root of the sum, which is the potential base, say for binary we have 1 + 2 + 4 + 8 + 16 = 31 (1^0 + 2^1 + 2^2 + 2^3 + 2^4), 16 dominates the total sum of the rest of the values, this is more obvious for higher bases. For the above example, the way to "guess" what's the base could be is to get the highest power which is 4, then calculate 31^(1/4) = 2.359... since it is bigger than 2, therefore we just guess the base maybe 2, and verify it.

    I think the confusing part of the code is this:

    if (r<5) break;
    

    This doesn't make too much sense, because the base between [2, 9] has been tested, we should change it to

    if (r < 10) break;
    

    Actually you can just get rid of the the base test for 2 - 10, and change this to:

    if (r < 2) break;
    

    I think there is another way to process this problem.
    say the minimum base is 2, the maximum number is 10 ^ 18, we can calculate the maximum number of 1s of base 2, which is the worse case.

    floor(log(n, 2))
    

    The maximum would be around 60, next step we just need to check which base satisfies.

    Hope it helps ;)


  • 0
    J

    @zhongyuan9817 @darren5
    This is a better explanation than my original post!
    My code shows my thoughts when trying to solve this problem. At first I just want to try r in range 2-n, but I would get TLE error for large n.
    we can arrange equitation sum = 1+r+r^2+r^3+...+r^p,
    to sum = (r^(p+1)-1)/(r-1), for very large r, sum is very close to r^p, so I thought it would be sufficient to just try a few r around sum^(1/p), in reality, I only tried r and got accepted.
    Someone might be able to mathematically prove the range of r around sum^(1/p) we need to test.

    if (r<5) break;
    

    is indeed misleading, but I just wanted to be safe, and save a little time of thinking about the edge cases.


  • 0
    Z

    @jinsheng yeah, very good strategy!


  • 0
    X

    This question is much more difficult in Java in order to pass all tests. It's easy or at most medium in Python (no need to worry about overflow) or C++ (just use long long). I'm not sure whether BigInteger is allowed in interview questions...


  • 0
    Z

    @XeHHXe very true, since the input is a string and we need to play with different base, when I first seen this question, I believe the real solution must not convert the input string, at least not convert the whole string to bigint/long long, so I added some comments to my python solution.

    # this is cheat
    n = int(n)
    

Log in to reply
 

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