N के नीचे प्रत्येक पूर्णांक को C++ में योग के रूप में व्यक्त करने के लिए आवश्यक न्यूनतम संख्याएँ

समस्या कथन

हमारे पास एक पूर्णांक N है। हमें N को K पूर्णांकों के योग के रूप में व्यक्त करने की आवश्यकता है जैसे कि इनमें से कुछ या सभी पूर्णांकों को जोड़कर हम 1 से N तक की सभी संख्याएँ प्राप्त कर सकते हैं। कार्य K का न्यूनतम मान ज्ञात करना है। /पी>

उदाहरण

यदि N =8 है तो अंतिम उत्तर यानी K होगा 3

यदि हम पूर्णांक 1, 2, 3 और 4 लेते हैं तो इनमें से कुछ या सभी समूहों को जोड़ने पर हम 1 से N तक की सभी संख्याएँ प्राप्त कर सकते हैं

e.g.
1 = 1
2 = 2
3 = 3
4 = 4
5 = 1 + 5
6 = 4 + 2
7 = 4 + 3
8 = 1 + 3 + 4

एल्गोरिदम

Count number of bits from given integer

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int getMinNumbers(int n) {
   int cnt = 0;
   while (n) {
      ++cnt;
      n = n >> 1;
   }
   return cnt;
}
int main() {
   int n = 8;
   cout << "Minimum required numbers = " <<getMinNumbers(n) << endl;
   return 0;
}

जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है

आउटपुट

Minimum required numbers = 4