Tìm binary gap

thang viết ngày 29/12/2018

Gần đây trong quá trình ôn lại cấu trúc dữ liệu giải thuật, có một bài test kỹ năng lập trình có yêu cầu input là một số nguyên dương (decime), output là số chữ số 0 lớn nhất được viết giữa hai số 1 trong dạng nhị phân (binary) của số đã nhập (input)

Có thể hình dung input và output như sau:

input: 12345678910
#binary = 100101101011010000111
output: 5

input: 12
#binary = 1100
output: 0

Mình có suy nghĩ 2 solution để giải quyết bài toán này:

1. Solution 1 Chuyển từ số decime sang dạng số binary bằng hàm cõ sẵn trong python. Tìm khoảng cách giữa 2 số 1 dài nhất trong dãy nhị phân, khoảng cách này chính là output cần tìm. Bên cạnh solution 1 thì có thêm biến thể Solution 1+.

2. Solution 2 Trong quá trình thực hiện phép chuyển từ decime sang binary sẽ thực hiện đếm giá trị 0, khi chuyển từ decime sang binary xong sẽ có kết quả luôn.

Đối với hướng 1, mình có trình bày bằng code python như dưới đây:

Solution 1

def binary_gap(N):
    binary = bin(N)[2:]
    #hàm này dùng để convert từ decime => binary
    #kết quả hàm này trả về dạng bắt đầu bằng 0b, nên dùng [2:]để loại bỏ phần này

    count = 0

    if binary.find("1") > 0:
        flag_1 = 1
    else:
        flag_1 = 0

    while(flag_1 >= 0):
        if count < binary.find("1", flag_1+1) - flag_1-1:
            count = binary.find("1", flag_1+1) - flag_1-1
        flag_1 = binary.find("1", flag_1+1)

    #print("Input = " +str(N) + " BIN = " + binary + " Output = " + str(count))
    #Hàm này để in kiểm tra kết quả
    return count

Ví dụ với đoạn code trên: thử với một vài kết quả số ngẫu nhiên

for i in range(5):
    print(binary_gap(random.randint(1,100000000000)))

Input = 68479289215 BIN = 111111110001101011110000011101111111 Output = 5
Input = 14388827016 BIN = 1101011001101001000001001110001000   Output = 5
Input = 48934584981 BIN = 101101100100101110101000001010010101 Output = 5
Input = 54337920123 BIN = 110010100110110010101101110001111011 Output = 3
Input = 50503643731 BIN = 101111000010010000000111001001010011 Output = 7

Thời gian chạy trung bình của chương trình trên là: O(l) với l là độ dài chuỗi nhị phân.

Mình có thử chạy với tập 10000 số từ 10,000,000,000 đến 10,000,010,000 thì thu được kết quả như ảnh dưới.
(Thời gian tính bằng milisecond)

Đối với hướng 2 mình có trình bày code ở đây:

Solution 2

def binary(N):
    count = 0
    result = 0
    i = 0

    #tmp = N

    while (N%2!=1):
        N = N>>1

    while(N>0):
        if N%2 == 1 :
            if result <= count:
                result = count
            count = 0
        else:
            count = count + 1
        i=i+1
        N = N>>1

    #print("Input = " +str(tmp) + " BIN = " + bin(tmp)[2:] + " Output = " + str(result))
    #Hàm này để in kiểm tra kết quả

    return result

Ví dụ với đoạn code trên: thử với một vài kết quả số ngẫu nhiên

for i in range(5):
    print(binary_gap(random.randint(1,100000000000)))

Input = 67999627914 BIN = 111111010101000101111111101010001010 Output = 3
Input = 46625933532 BIN = 101011011011000111110100100011011100 Output = 3
Input = 14339787699 BIN = 1101010110101101111100101110110011   Output = 2
Input = 36030043321 BIN = 100001100011100011101101010010111001 Output = 4
Input = 52212838152 BIN = 110000101000001000001010111100001000 Output = 5

Thời gian chạy trung bình của chương trình trên là: O(l) với l là độ dài chuỗi nhị phân.
Mình có thử chạy với tập 10000 số từ 10,000,000,000 đến 10,000,010,000 thì thấy thời gian nó gần như hội tụ lại như ảnh dưới.
(Thời gian tính bằng milisecond)

Đến đây thì có thể thấy một điều là solution 2 có thời gian chạy tốt hơn hẳn solution 1, và độ ổn định cũng tốt hơn rất nhiều.
Liệu có phải ở solution 1 do sử dụng hàm bin() có sẵn nên tốc độ bị chậm đi hay không ?

Từ solution 1, theo gợi ý của một bạn, mình có code một biến thể khác:

Solution 1+

def binary_gap_imp(N):
    while (N%2!=1):
        N = N>>1
    result = len(max((bin(N)[2:].split('1'))))
    #Dòng code này thực hiện tính độ dài chuỗi lớn nhất, trong các chuỗi chứa số 0 được tách từ dãy só nhị phân.

    #print("Input = " +str(N) + " BIN = " + bin(N)[2:] + " Output = " + str(result))
    #Hàm này để in kiểm tra kết quả
    return result

Ví dụ với đoạn code trên: thử với một vài kết quả số ngẫu nhiên

for i in range(5):
    print(binary_gap(random.randint(1,100000000000)))

Input = 7059652734  BIN = 110100100110010011100000001111110     Output = 7
Input = 39602050260 BIN = 100100111000011101110101010011010100  Output = 4
Input = 65158925666 BIN = 111100101011110001100100110101100010  Output = 3
Input = 54479348279 BIN = 110010101111001110001110001000110111  Output = 3
Input = 94928399254 BIN = 1011000011010001011000110101110010110 Output = 4

Thời gian chạy trung bình của chương trình trên là: O(l) với l là độ dài chuỗi nhị phân.
Mình có thử chạy với tập 10000 số từ 10,000,000,000 đến 10,000,010,000 thì thấy thời gian nó gần như hội tụ lại như ảnh dưới.

(Thời gian tính bằng milisecond)

Qua 3 hình trên có thể thấy có sự khác biệt rất lớn khi N lớn.
Và đặc biệt hơn có thể đưa ra 1 kết luận, việc dùng hàm có sẵn của python sẽ làm chương trình tính toán nhanh hơn.

Bạn nào có solution tốt hơn thì đề xuất để mình học hỏi với nhé.