A solution that I arrived with is by using two pointers. I noticed a repeating pattern as the n increases. The main idea is string after the middle of string will always be the same for the next n. n=2 -- 01**1** n=3 -- 0111**001** n=4 -- 011100110110**001** meaning that we only have to compute the inversion from the current middle pointer to the previous n middle pointer. def findKthBit(self, n: int, k: int) -> str: cur = "011" length = 3 left = 2 right = 2 while length < k: length = length*2 + 1 right *= 2 cur += "1" + cur[:left-2:-1].replace('1', '2').replace('0', '1').replace('2', '0') + cur[left:] left = right return cur[k-1] To prevent crash, I started at n=2. With addition to early stop to the loop, this solution beats 100% (11ms) on my end.
this is log(k) both space and time idk why its not in the editorial: def dfs(i): if i == 1: return 0 if math.log2(i) == math.ceil(math.log2(i)): return 1 mid = 2 ** math.floor(math.log2(i)) new_i = 2 * mid - i return 1 if dfs(new_i) == 0 else 0 return str(dfs(k))
Well, it's predictable, if you check the editorial that's being added to problems you'll notice the new problems editorials, and for ones that already have editorial, you can get an idea of them by checking the monthly topics section, each week focuses on a set of topics
val = ["0"] def convert(s): return ["0" if num == "1" else "1" for num in s][::-1] for _ in range(n): prev = val[:] val = val + ["1"] + convert(prev) return val[k-1]
Leetcode posts editorials for daily problems some time before they release it as a daily problem, you can filter the editorials get recent published editorials to get know which problem will be the daily problem next.
