এখানে আমরা একটি আকর্ষণীয় সমস্যা দেখব সেট-বিটস alapján অ্যারে সর্ট করার সম্পর্কে। যখন অ্যারেতে একটি এলিমেন্টের সেট-বিটস বেশি, তবে সেটি অন্য এলিমেন্টের চেয়ে আগে প্লেস হবে যার সেট-বিটস কম। মনে করুন কিছু সংখ্যা 12, 15, 7। সেট বিটস মূলত তাদের বাইনারি রিপ্রেজেন্টেশনে ১ গুলোর সংখ্যা। এগুলো হল 1100 (12), 1111 (15), এবং 0111 (7)। তাই সর্ট করার পর এটি হবে -
1111, 0111, 1100 (15, 7, 12)
এখানে আমাদের প্রথমে সেট-বিটস সংখ্যা বের করতে হবে। তারপর আমরা C++ STL সর্ট ফাংশন ব্যবহার করব সেগুলো সর্ট করার জন্য। আমাদের সেট-বিট কাউন্টস ভিত্তিক করে কমপারিজন লজিক তৈরি করতে হবে।
অ্যালগরিদম
getSetBitCount(number):
শুরু
count := 0
যতক্ষণ number ০ না হয়, করো
যদি number AND 1 = 1, তবে
count ১ বাড়াও
number = number কে এক বিট রাইট শিফ্ট করো
শেষ
count রিটার্ন করো
শেষ
compare(num1, num2):
শুরু
count1 = getSetBitCount(num1)
count2 = getSetBitCount(num2)
যদি count1 <= count2, তবে false রিটার্ন করো, অন্যথায় true রিটার্ন করো
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <algorithm>
using namespace std;
int getSetBitCount(int number) {
int count = 0;
while(number) {
if(number & 1 == 1)
count++;
number = number >> 1; // 넘্বার কে এক বিট রাইট শিফ্ট করো
}
return count;
}
int compare(int num1, int num2) {
int count1 = getSetBitCount(num1);
int count2 = getSetBitCount(num2);
if(count1 <= count2)
return 0;
return 1;
}
main() {
int data[] = {2, 9, 4, 3, 5, 7, 15, 6, 8};
int n = sizeof(data)/sizeof(data[0]);
sort(data, data + n, compare);
for(int i = 0; i < n; i++) {
cout << data[i] << " ";
}
}
আউটপুট
15 7 9 3 5 6 2 4 8
