สมมติว่าเรามีตัวเลข N เราต้องหาระยะห่างมากที่สุดระหว่าง 1 ติดกันสองตัวในรูปแบบไบนารี ถ้าไม่มี 1 สองตัวติดกันให้คืน 0
เช่น 71 ผลลัพธ์คือ 4 เพราะ 71 ในไบนารีคือ 1000111 มี 1 4 ตัว 1 ตัวแรกและตัวที่สองห่างกัน 4 ตำแหน่ง ที่เหลือห่างกัน 1 ตำแหน่ง ดังนั้นระยะห่างมากที่สุดคือ 4
ขั้นตอนการแก้ปัญหา
- K = ลิสต์บิตของรูปแบบไบนารีของ N
- Max = 0, C = 0, S = 0, Flag = False
- วนลูป i จาก 0 ถึง len(K)-1:
- ถ้า K[i] == '1' และ C == 0 และ Flag == False: C = i, Flag = True (เจอ 1 ตัวแรก)
- มิฉะนั้นถ้า K[i] == '1' และ Flag: S = i; ถ้า Max < |S-C|: Max = |S-C|; C = S (อัปเดตระยะห่างและตำแหน่ง 1 ล่าสุด)
- คืน Max
ตัวอย่างโค้ด
def solve(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 == 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
n = 71
print(solve(n))
ข้อมูลเข้า
71
ข้อมูลออก
4
