समस्या कथन
दो नंबर n और k को देखते हुए, हमें दी गई संख्या को अधिकतम करने के लिए आवश्यक फ़्लिप की न्यूनतम संख्या को इसके बिट्स को फ़्लिप करके खोजने की आवश्यकता है जैसे कि परिणामी संख्या में k सेट बिट्स हों। कृपया ध्यान दें कि इनपुट को इस शर्त को पूरा करना चाहिए कि k
उदाहरण
मान लीजिए n =9 और k =2
9 का बाइनरी प्रतिनिधित्व -1001 है। इसमें 4 बिट होते हैं।
2 सेट बिट्स के साथ 4 अंकों की सबसे बड़ी बाइनरी संख्या है - 1100 यानी 12
1001 को 1100 में बदलने के लिए हमें हाईलाइट किए गए 2 बिट्स को फ्लिप करना होगा
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
एल्गोरिदम
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.
उदाहरण
#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;
} आउटपुट
Minimum required flips: 2