আমাদেরকে একটি পূর্ণসংখ্যার সংখ্যা দেওয়া হয়েছে ধরা যাক, 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