समस्या कथन
दो नंबर n और k दिए गए हैं, हमें दिए गए नंबर को उसके बिट्स फ्लिप करके अधिकतम करने के लिए आवश्यक न्यूनतम फ्लिप्स की संख्या ढूंढनी है जैसे कि परिणामी नंबर में ठीक k सेट बिट्स हों। कृपया ध्यान दें कि इनपुट को कंडीशन पूरी करनी चाहिए कि k, n में बिट्स की संख्या से कम हो।
उदाहरण
मान लीजिए n = 9 और k = 2
9 का बाइनरी प्रतिनिधित्व - 1001। इसमें 4 बिट्स हैं।
2 सेट बिट्स के साथ सबसे बड़ा 4 डिजिट बाइनरी नंबर - 1100 यानी 12
1001 को 1100 में बदलने के लिए हमें हाइलाइटेड 2 बिट्स फ्लिप करने होंगे
एल्गोरिदम
1. n में बिट्स की संख्या गिनें। इस वेरिएबल को bitCount कहें। हम मैथ लाइब्रेरी से log2(n) फंक्शन का उपयोग इस प्रकार कर सकते हैं: bitCount = log2(n) + 1; 2. k सेट बिट्स के साथ सबसे बड़ी संख्या ढूंढें: maxNum = pow(2, k) - 1; 3. n के समान बिट्स की संख्या और k सेट बिट्स के साथ सबसे बड़ी संभावित संख्या ढूंढें: maxNum = maxNum << (bitCount - k); 4. (n ^ maxNum) की गणना करें और सेट बिट्स की संख्या गिनें।
उदाहरण
#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
