Tuyên bố vấn đề
Cho hai số n và k, chúng ta cần tìm số lần lật nhỏ nhất cần thiết để tối đa hóa số đã cho bằng cách lật các bit của nó sao cho số kết quả có đúng k bit đặt. Xin lưu ý rằng đầu vào phải thỏa mãn điều kiện k
Ví dụ
Giả sử n =9 và k =2
Biểu diễn nhị phân của 9 là - 1001. Nó chứa 4 bit.
Số nhị phân 4 chữ số lớn nhất với 2 bit đặt là - 1100 tức là 12
Để chuyển đổi 1001 thành 1100, chúng ta phải lật 2 bit được canh lề cao
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Thuật toán
1. Count the number of bits in n. Let us call this variable as bitCount. we can use log2(n) function from math library as fllows:
bitCount = log2(n) + 1;
2. Find largest number with k set bits as follows: maxNum = pow(2, k) - 1;
3. Find the largest number possible with k set bits and having exactly same number of bits as n as follows:
maxNum = maxNum << (bitCount - k);
4. Calculate (n ^ maxNum) and count number of set bits.
Ví dụ
#include <iostream>
#include <cmath>
using namespace std;
int getSetBits(int n){
int cnt = 0;
while (n) {
++cnt;
n = n & (n - 1);
}
return cnt;
}
int minFlipsRequired(int n, int k){
int bitCount, maxNum, flipCount;
bitCount = log2(n) + 1;
maxNum = pow(2, k) - 1;
maxNum = maxNum << (bitCount - k);
flipCount = n ^ maxNum;
return getSetBits(flipCount);
}
int main(){
cout << "Minimum required flips: " << minFlipsRequired(9, 2) << "\n";
return 0;
} Đầu ra
Minimum required flips: 2