Giả sử chúng ta có một số nguyên dương N, ta cần tìm khoảng cách lớn nhất giữa hai bit 1 liên tiếp trong biểu diễn nhị phân của N. Nếu không có hai bit 1 liên tiếp nào, trả về 0.
Ví dụ, nếu đầu vào là 22, đầu ra sẽ là 2, vì 22 trong nhị phân là 10110. Có ba bit 1 trong biểu diễn nhị phân của 22, và hai cặp bit 1 liên tiếp. Cặp đầu tiên có khoảng cách 2, cặp thứ hai có khoảng cách 1. Kết quả là khoảng cách lớn nhất trong hai khoảng cách này, tức là 2.
Để giải quyết bài toán này, ta thực hiện các bước sau:
- K := tạo danh sách các bit của biểu diễn nhị phân của N
- Max := 0, C := 0, S := 0
- Flag := False
- Với i từ 0 đến kích thước của K, thực hiện:
- Nếu K[i] là '1' và C là 0 và Flag là False, thì:
- C := i
- Flag := True
- Ngược lại, nếu K[i] là '1' và Flag là True, thì:
- S := i
- Nếu Max < |S - C|, thì:
- Max := |S - C|
- C := S
- Nếu K[i] là '1' và C là 0 và Flag là False, thì:
- Trả về Max
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
class Solution: def binaryGap(self, N): B = bin(N).replace('0b','') K = str(B) K = list(K) Max = 0 C = 0 S = 0 Flag = False for i in range(len(K)): if K[i] == '1' and C == 0 and Flag is False: C = i Flag = True elif K[i] == '1' and Flag: S = i if Max < abs(S - C): Max = abs(S - C) C = S return Max ob = Solution() print(ob.binaryGap(22))Đầu vào
22
Đầu ra
2