Xóa một bit khỏi số nhị phân để được giá trị lớn nhất bằng C++

Cho chuỗi nhị phân, xóa đúng 1 bit sao cho số còn lại (theo giá trị nhị phân) lớn nhất. Ví dụ:

Input: 1011 → Output: 111 (xóa bit 0) Input: 111 → Output: 11 (xóa bit bất kỳ)

Thuật toán tham lam O(n)

Duyệt từ trái sang (bit cao đến thấp). Gặp bit '0' đầu tiên → xóa nó (bỏ qua), dừng. Nếu không có bit 0 → xóa bit cuối cùng.

Ví dụ

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

int main() {
    string str = "1011";
    bool flag = false;
    int n = str.length();
    char res[n - 1];
    int j = 0;
    for (int i = 0; j < n - 1; i++) {
        if (str[i] == '0' && !flag) { flag = true; continue; }
        else res[j++] = str[i];
    }
    cout << "Maximum number: " << res;
    return 0;
}

Kết quả

Maximum number: 111

Kết luận

Xóa bit 0 đầu tiên từ trái (MSB) để tối đa hóa giá trị nhị phân. Code C++ O(n).