Problem statement
ให้ตัวเลข n และ k เราต้องหาจำนวนการพลิกบิต (bit flips) น้อยที่สุดเพื่อทำให้ตัวเลขที่ได้มีค่ามากที่สุดและมี set bits เท่ากับ k อย่างแน่นอน โปรดทราบว่า input ต้องเงื่อนไข k < จำนวนบิตใน n
Example
- สมมติ n = 9 และ k = 2
- Binary representation of 9 คือ − 1001 มี 4 บิต
- เลข binary 4 หลักที่มี 2 set bits มากที่สุดคือ − 1100 คือ 12
- เพื่อแปลง 1001 เป็น 1100 ต้องพลิกบิตที่ไฮไลท์ 2 บิต
อัลกอริทึม
1. นับจำนวนบิตใน n เรียกตัวแปรนี้ว่า bitCount ใช้ log2(n) จาก math library: bitCount = log2(n) + 1; 2. หาเลขที่ใหญ่ที่สุดกับ k set bits ดังนี้: maxNum = pow(2, k) - 1; 3. หาเลขที่ใหญ่ที่สุดที่เป็นไปได้กับ k set bits และมีจำนวนบิตเท่ากับ n ดังนี้: maxNum = maxNum << (bitCount - k); 4. คำนวณ (n ^ maxNum) และนับจำนวน set bits
ตัวอย่าง
#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; }ผลลัพธ์
When you compile and execute above program. It generates following output −
Minimum required flips: 2
