সমস্যা বিবরণ
একটি ইন্টিজার N দেওয়া আছে। N কে K সংখ্যক ইন্টিজারের যোগফল হিসেবে এক্সপ্রেস করতে হবে যাতে এই ইন্টিজারগুলো থেকে কিছু বা সব যোগ করে ১ থেকে N পর্যন্ত সব সংখ্যা পাওয়া যায়। K-এর ন্যূনতম মান বের করতে হবে।
উদাহরণ
N = 8 হলে চূড়ান্ত উত্তর K = 3।
যদি ১, ২, ৩, ৪ ইন্টিজার নেওয়া হয়, তবে এগুলো যোগ করে ১ থেকে N পর্যন্ত সব সংখ্যা পাওয়া যায়।
e.g. 1 = 1 2 = 2 3 = 3 4 = 4 5 = 1 + 5 6 = 4 + 2 7 = 4 + 3 8 = 1 + 3 + 4
অ্যালগরিদম
দেওয়া ইন্টিজারের বিট সংখ্যা গণনা করুন।
উদাহরণ
#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
