আমাদেরকে একটি পূর্ণসংখ্যার সংখ্যা দেওয়া হয়েছে ধরা যাক, N যেটিকে একটি ভাজক হিসাবে বিবেচনা করা হয় এবং এটি 1 - N থেকে শুরু হওয়া সংখ্যাগুলি দিয়ে ভাগ করা হবে এবং কাজটি হল সেইসব ভাজকের সংখ্যা গণনা করা যেখানে সেট বিটের সংখ্যা বেশি। ভাগফল যখন প্রদত্ত সংখ্যা N দিয়ে ভাগ করা হয়।
উদাহরণস্বরূপ
ইনপুট - int N =6
আউটপুট - N ভাগ করার ক্ষেত্রে ভাগফলের চেয়ে বেশি সেট বিট বিশিষ্ট ভাজকের সংখ্যা হল:5
ব্যাখ্যা - প্রথমত, আমরা 1 - N থেকে শুরু হওয়া সংখ্যাগুলির সাথে N সংখ্যাটিকে ভাগ করব এবং ভাজকের সেট বিট এবং ভাগফল অর্থাৎ
1-> N =6 /1(1) =6(2) =1 <2 =বিবেচিত নয়
2-> N =6 /2(1) =3(2) =2 =2 =বিবেচিত
3-> N =6 /3(2) =2(1) =2> 1 =বিবেচিত
4-> N =6 /4(1) =1(1) =1 =1 =বিবেচিত
5-> N =6 /5(2) =1(1) =2> 1 =বিবেচিত
6-> N =6 /6(2) =1(1) =2>1 =বিবেচিত
আমরা দেখতে পাচ্ছি, আমরা বিবেচনা করা কেস নেব এবং আউটপুট হবে 5।
ইনপুট - int N =10
আউটপুট - N ভাগ করার ক্ষেত্রে ভাগফলের চেয়ে বেশি সেট বিট বিশিষ্ট ভাজকের সংখ্যা হল:8
ব্যাখ্যা - প্রথমত, আমরা 1 - N থেকে শুরু হওয়া সংখ্যাগুলির সাথে N সংখ্যাটিকে ভাগ করব এবং ভাজকের সেট বিট এবং ভাগফল অর্থাৎ
1-> N =10 /1(1) =10(2) =1 <2 =বিবেচিত নয়
2-> N =10 /2(1) =5(2) =2 =2 =বিবেচিত
3-> N =10 /3(2) =3(2) =2 =2 =বিবেচিত
4-> N =10 /4(1) =2(1) =1 <2 =বিবেচিত নয়
5-> N =10 /5(2) =2(1) =2> 2 =বিবেচিত
6-> N =10 /6(2) =1(1) =2>1 =বিবেচিত
7-> N =10 /7(3) =1(1) =3>1 =বিবেচিত
8-> N =10 /8(1) =1(1) =1 =1 =বিবেচিত
9-> N =10 /9(2) =1(1) =2> 2 =বিবেচিত
10-> N =10 /10(2) =1(1) =2> 1 =বিবেচিত
আমরা দেখতে পাচ্ছি, আমরা বিবেচনা করা কেস নেব এবং আউটপুট হবে 8।
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
- একটি ধনাত্মক পূর্ণসংখ্যা N ইনপুট করুন এবং এটিকে একটি আর্গুমেন্ট হিসাবে divisors_quotient() ফাংশনে পাস করুন৷
- ভাজক_কোটেন্ট()
- ফাংশনের ভিতরে
- N রিটার্ন করুন - সেট_quo(N) + 1 ফাংশনে কল করুন এবং সেট_quo() ফাংশনে যান
- ফাংশনের ভিতরে set_quo()
- শুরু এবং শেষ হিসাবে একটি অস্থায়ী পরিবর্তনশীল তৈরি করুন এবং 1 দিয়ে শুরু করুন এবং sqrt(N) দিয়ে শেষ করুন।
- শুরু পর্যন্ত লুপ শুরু করুন <শেষ পর্যন্ত এবং টেম্প হিসাবে একটি অস্থায়ী ভেরিয়েবল তৈরি করুন এবং এটিকে সেট করুন (শুরু + শেষ) / 2
- IF চেক করুন (ফাংশনে কল করুন verify() এবং temp এবং N একটি আর্গুমেন্ট হিসাবে পাস করুন) তারপর টেম্প হিসাবে শেষ সেট করুন
- অন্যথা, টেম্প + 1 হিসাবে শুরু সেট করুন
- IF(!ফাংশনে কল করুন verify() এবং temp এবং N একটি আর্গুমেন্ট হিসাবে পাস করুন) তারপর start + 1 ফেরত দিন।
- অন্যথায়, ফিরতে শুরু করুন
- ফাংশনের ভিতরে verify()
- IF(ফাংশনে কল val_bit(temp/val) ফাংশন val_bit(val) তে কলের চেয়ে কম তা পরীক্ষা করুন) তারপর সত্য ফেরত দিন অন্যথায় মিথ্যা দিন
- ভাল_বিট()
- ফাংশনের ভিতরে
- ফলাফল সংরক্ষণ করার জন্য একটি অস্থায়ী পরিবর্তনশীল গণনা ঘোষণা করুন।
- স্টার্ট লুপ যখন ভ্যালের মান থাকে। লুপের ভিতরে, val / 2 হিসাবে সেট করুন এবং 1 দ্বারা গণনা বাড়ান।
- রিটার্ন গণনা।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int val_bit(int val) {
int count = 0;
while (val) {
val = val / 2;
count++;
}
return count;
}
bool verify(int val, int temp) {
if (val_bit(temp / val) <= val_bit(val)) {
return true;
}
return false;
}
int set_quo(int N) {
int start = 1;
int end = sqrt(N);
while (start < end) {
int temp = (start + end) / 2;
if (verify(temp, N)) {
end = temp;
} else {
start = temp + 1;
}
}
if (!verify(start, N)) {
return start + 1;
} else {
return start;
}
}
int divisors_quotient(int N) {
return N - set_quo(N) + 1;
}
int main() {
int N = 10;
cout << "Count of divisors having more set bits than quotient on dividing N are: " << divisors_quotient(N);
return 0;
} যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেআউটপুট
Count of divisors having more set bits than quotient on dividing N are: 8
