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

0:00 - Read the problem
0:30 - Drawing Explanation
14:36 - Coding Explanation
18:13 - Coding Explanation 2

leetcode 1545

#neetcode #leetcode #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.

[debrajkundu]

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

[ThinkOutsideTheBox]

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

[mitratiwari]

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

[pastori]

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

[IK-xkex]

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

[rahulsihara]

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

[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]

[Graveness]

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