Find Kth Bit in Nth Binary String - Leetcode 1545 - Python

[@AlfredPros]

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.

[@debrajkundu2780]

I cached all strings outside the class and Runtime reduced from 537ms -> 51ms

[@prajwals8203]

you are a freaking genius

[@dampdigits.69]

I didn't and my run-time was 0ms in python

[@baetz2]

you can also hardcode the result as a big number for n=20 and return the kth bit of that number in 0ms, it will work for every n from 1 to 20

[@prajwals8203]

@@baetz2 Java?

[@ThinkOutsideTheBox12345]

Thanks for this video, the way you explain problems is brilliant!

[@mitratiwari5035]

I am a beginner and started doing leetcode recently, your videos really helped me understand and write efficient code. Thanks 😄

[@MP-ny3ep]

Terrific explanation !

[@pastori2672]

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))

[@ksaigon]

Bro must be predicting these daily questions there's no way

[@hithambasheir3283]

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

[@IK-xk7ex]

Inversion function is f(x) = 1-x where x={0,1}

[@tejas1531]

Thanku soooooooooo much!!

[@ThinkOutsideTheBox12345]

Great video!

[@bobyoutube2117]

Just simulating works as well

[@rahulsihara8946]

what going with quick uploads ? i didn't even get time to read the question.

[@abhivardhan395]

Best.....

[@kitt-u8r]

beats 100% !!!!! ,hurehhhhh

[@amitgoyal8760]

Wtf man this speed is

[@princeakhil208]

Wow this is super fast

[@higuys450]

I just woke up bro

[@albin_joby]

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]

[@SidhanthSanil]

beauty

[@bhanunani1307]

how to be like him😬😭

[@Graveness4920]

How did you know the question beforehand to release the video exactly at 00:00 UTC?

[@31redorange08]

He activated cheats.

[@zweitekonto9654]

Ain't know way what

[@vuduongcong1320]

you can change the timezone and get the question bf your midnight

[@blue5887]

he's already solved these questions, when it comes up again as a daily problem he just uploads the video that he's already made on that problem

[@aayushtheapple]

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.