Số bước để giảm số trong biểu diễn nhị phân xuống 1 trong C++

Giới thiệu

Cho một số s dưới dạng nhị phân. Ta cần tìm số bước để giảm nó xuống 1 theo các quy tắc sau:

• Nếu số hiện tại là chẵn, chia nó cho 2.
• Nếu số hiện tại là lẻ, cộng 1 vào nó.

Ví dụ: đầu vào "1101" (thập phân là 13). Các bước thực hiện:

1. 13 lẻ → +1 = 14
2. 14 chẵn → /2 = 7
3. 7 lẻ → +1 = 8
4. 8 chẵn → /2 = 4
5. 4 chẵn → /2 = 2
6. 2 chẵn → /2 = 1

Tổng cộng 6 bước.

Thuật toán

Giải pháp sử dụng phép cộng nhị phân và mô phỏng quy trình:

1. Chuyển chuỗi nhị phân thành vector các bit (0/1).
2. Lặp cho đến khi vector chỉ còn 1 phần tử:
   • Tăng bộ đếm bước.
   • Nếu bit cuối (LSB) là 0 (số chẵn) → xóa bit cuối (chia 2).
   • Nếu bit cuối là 1 (số lẻ) → cộng 1 vào số nhị phân (sử dụng hàm addBinary).
3. Trả về bộ đếm.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string addStrings(vector<int> num1, vector<int> num2) {
        vector<int> ret;
        int carry = 0, sum = 0;
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int i = 0, j = 0;
        while (i < num1.size() || j < num2.size()) {
            if (i < num1.size() && j < num2.size()) {
                sum = carry + num1[i] + num2[j];
                ret.push_back(sum % 2);
                carry = sum / 2;
                i++; j++;
            } else if (i < num1.size()) {
                sum = carry + num1[i];
                ret.push_back(sum % 2);
                carry = sum / 2;
                i++;
            } else {
                sum = carry + num2[j];
                ret.push_back(sum % 2);
                carry = sum / 2;
                j++;
            }
        }
        if (carry) ret.push_back(carry);
        string ans = "";
        for (int k = ret.size() - 1; k >= 0; k--)
            ans += (ret[k] + '0');
        return ans.empty() ? "0" : ans;
    }

    string addBinary(vector<int>& a, vector<int>& b) {
        return addStrings(a, b);
    }

    vector<int> makeVector(string v) {
        vector<int> ret;
        for (char c : v) ret.push_back(c - '0');
        return ret;
    }

    int numSteps(string s) {
        int ret = 0;
        vector<int> x = makeVector(s);
        while (x.size() > 1) {
            ret++;
            if (x.back() == 0) {
                x.pop_back(); // chia 2
            } else {
                vector<int> temp(1, 1); // số 1
                x = makeVector(addBinary(x, temp)); // cộng 1
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.numSteps("1101"); // Output: 6
    return 0;
}

Phân tích độ phức tạp

• Thời gian: O(n²) trong trường hợp xấu nhất do phép cộng nhị phân lặp lại.
• Không gian: O(n) để lưu vector bit.

Lưu ý

Có thể tối ưu bằng cách xử lý trực tiếp trên chuỗi hoặc sử dụng toán tử bitwise nếu số vừa trong kiểu dữ liệu chuẩn. Tuy nhiên, bài toán yêu cầu xử lý chuỗi nhị phân dài.