Thảo luận về một vấn đề trong đó chúng ta được cho một số nhị phân. Chúng tôi phải xóa một chút khỏi nó để số còn lại phải là số tối đa của tất cả các tùy chọn khác, chẳng hạn như
Input : N = 1011 Output: 111 Explanation: We need to remove one bit so removing 0 bit will give a maximum number than removing any 1’s bit. 111 > 101, 011. Input: 111 Output: 11 Explanation: Since all the bits are 1 so we can remove any bit.
Phương pháp tiếp cận để tìm giải pháp
Phương pháp Brute-Force
Việc áp dụng bạo lực sẽ cung cấp số lượng kết quả tối đa, tức là bằng cách loại bỏ từng bit một, so sánh các kết quả khác nhau và nhận được kết quả tối đa.
Nhưng có một Cách tiếp cận hiệu quả mà nó có thể sử dụng, tức là, nếu chúng ta loại bỏ bit dư thừa ít nhất.
Phương pháp tiếp cận hiệu quả
Cách tiếp cận hiệu quả sẽ ảnh hưởng ít nhất đến số lượng kết quả.
-
Đầu tiên, lướt qua các bit từ bên phải.
-
Tìm kiếm 0 và xóa nó trên quầy đầu tiên.
-
Nếu không tìm thấy 0, hãy xóa bất kỳ bit nào.
Ví dụ
Mã C ++ cho phương pháp tiếp cận hiệu quả
#include <bits/stdc++.h>
using namespace std;
int main(){
string str = "1011";
bool flag = false;
int n = str.length();
// Initialising new array for
char res[n - 1];
int j = 0;
// traversing through the binary number from right.
for (int i = 0; j < n - 1; i++) {
// if 0 is found then skip it.
if (str[i] == '0' && flag == false) {
flag = true;
continue;
}
else
res[j++] = str[i];
}
// printing the resulting string.
cout << "Maximum number: " << res;
return 0;
} Đầu ra
Maximum number: 111
Giải thích về Quy tắc trên
-
Một biến cờ được sử dụng để chỉ có một số 0 bị loại bỏ.
-
Res mảng ký tự được khởi tạo để lưu trữ số kết quả.
-
Vòng lặp sẽ chạy đến n-1 vì chúng ta cần lưu trữ một phần tử ít hơn số ban đầu.
Kết luận
Trong hướng dẫn này, chúng tôi đã thảo luận về việc tìm số tối đa sau khi xóa một bit khỏi nó. Chúng tôi đã thảo luận về hai cách tiếp cận để giải quyết vấn đề này.
Chúng tôi cũng viết Mã C ++ tương tự, chúng tôi có thể viết bằng bất kỳ ngôn ngữ nào khác như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.