@StefanPochmann That's an elegant solution. I am just wondering what would be the time complexity of this?
harshaneel
@harshaneel
Posts made by harshaneel

RE: Simple Python

RE: Java TreeSet log(n) Solution with explanation
@sheva Oh yes. You have mentioned that in the last line. Missed that.

RE: Java TreeSet log(n) Solution with explanation
Just curious how come this is O(log n) solution? If you are scanning all the houses shouldn't it be O(n) solution?

RE: Python solution with detailed mathematical explanation and derivation
@StefanPochmann Yeah I accidentally removed it. Added it again with some more comments and references.

RE: Python solution with detailed mathematical explanation and derivation
@StefanPochmann Thanks for your inputs! I will take that in account.

Python solution with detailed mathematical explanation and derivation
First things first. Let's see the math behind it.
From given information, we can say one thing Numbers will be of form
n = k^m + k^(m1) + ... + k + 1
=> n1 = k^m + k^(m1) + ... + k
=> n1 = k (k^(m1) + k^(m2) + ... + k + 1) ...... [1]Also, from n = k^m + k^(m1) + ... + k + 1, we can say,
nk^m = k^(m1) + k^(m2) + ... + k + 1 ...... [2]from [1] and [2],
n1 = k (n  k^m)
=>k^(m+1) = nk  n + 1if you shuffle sides you will end up getting following form,
(k^(m+1)  1)/(k  1) = n .... [3]
Also from [1] note that, (n  1) must be divisible by k.
We know that, n = k^m + k^(m1) + ... + k + 1
=> n > k^m
=> mth root of n > k .... [4][EDIT] >
With inputs from @StefanPochmann we can also say, from binomial thorem, n = k^m + ... + 1 < (k+1)^m .... [5]
Therefore, k+1 > mth root of n > k. .... from [4] and [5]
Thus ⌊mth root of n⌋ is the only candidate that needs to be tested. [6]<
So our number should satisfy this equation where k will be our base and m will be (number of 1s  1)
This brings us to the search problem where we need to find k and m.
Linear search from 1 to n does not work. it gives us TLE. So it leaves us with performing some optimization on search space.
From [6] we know that the only candidate that needs to be tested is, ⌊mth root of n⌋
We also know that the smallest base is 2 so we can find our m must be between 2 and log_{2}n else m is (n1) [7]
That brings me to the code:
[EDIT]  >import math class Solution(object): def smallestGoodBase(self, n): """ :type n: str :rtype: str """ n = int(n) max_m = int(math.log(n,2)) # Refer [7] for m in range(max_m,1,1): k = int(n**m**1) # Refer [6] if (k**(m+1)1)//(k1) == n: # Refer [3] return str(k) return str(n1)
<—

RE: Java Short DFS Solution
@sankalp6 @shawngao I did some research about it and I think I know now why that happens. Python is a dynamic language, unlike Java. Java has Tail Recursion Optimization which is optimized by the compiler. Follow this thread from StackOverflow for more info. In my implementation, there is tail recursion which makes this super slow.
Something to keep in mind for next time.

RE: Java Short DFS Solution
@shawngao Thank you for your solution. I am doing the exact same thing in Python. I have no idea why I am getting Time Limit Exceeded! Can you help with that? Here is my code:
class Solution(object): def findTargetSumWays(self, nums, S): """ :type nums: List[int] :type S: int :rtype: int """ return self.find_target(nums,S,0) def find_target(self,nums,S,i): if i == len(nums): if S == 0: return 1 else: return 0 else: return self.find_target(nums,S+nums[i],i+1) + self.find_target(nums,Snums[i],i+1)

RE: 2 lines Python, 2 ways
@StefanPochmann Thanks for your elegant solution. I just want to know what made you think about median? Initially I was thinking exactly same way and only difference was I was taking round(mean) which was obviously failing some test cases.