ধারণা
আমাদের n সংখ্যার একটি অ্যারে আছে, যেখানে n সর্বাধিক 32,000। এখন প্রদত্ত অ্যারের ডুপ্লিকেট এন্ট্রি থাকতে পারে এবং আমরা জানি না n কী। এখন প্রশ্ন উঠেছে যে মাত্র 4 কিলোবাইট মেমরি উপলব্ধ থাকলে, অ্যারের সমস্ত ডুপ্লিকেট উপাদানগুলি কীভাবে প্রদর্শন বা প্রিন্ট করবে?
ইনপুট
arr[] = {2, 6, 2, 11, 13, 11}
আউটপুট
2 11 2 and 11 appear more than once in given array.
ইনপুট
arr[] = {60, 50, 60}
আউটপুট
60
পদ্ধতি
এখন আমাদের কাছে 4 কিলোবাইট মেমরি রয়েছে যা নির্দেশ করে যে আমরা 8 * 4 * 210 বিট পর্যন্ত অ্যাড্রেস করতে পারি। এটা উল্লেখ্য যে 32 * 210 বিট 32000 এর চেয়ে বড়। তাই আমরা 32000 বিট দিয়ে একটি বিট তৈরি করতে পারি, যেখানে প্রতিটি বিট একটি পূর্ণসংখ্যার প্রতিনিধিত্ব করে। .
আবার উল্লেখ করা উচিত যে যদি আমাদের 32000-এর বেশি বিট দিয়ে একটি বিট জেনারেট করার প্রয়োজন হয় তবে আমরা সহজেই 32000-এর বেশি বিট তৈরি করতে পারি; এই বিট ভেক্টরটি প্রয়োগ করে, আমরা অ্যারের মাধ্যমে পুনরাবৃত্তি করতে সক্ষম হতে পারি, বিট v এ 1 সেট করে প্রতিটি উপাদান v ফ্ল্যাগ করে।
উদাহরণ
// C++ program to print all Duplicates in array #include <bits/stdc++.h> using namespace std; // Shows a class to represent an array of bits using // array of integers class BitArray{ int *arr1; public: BitArray() {} // Constructor BitArray(int n1){ // Used to divide by 32. To store n bits, we require // n/32 + 1 integers (Assuming int is stored // using 32 bits) arr1 = new int[(n1 >> 5) + 1]; } // Now get value of a bit at given position bool get(int pos1){ // Used to divide by 32 to find position of // integer. int index1 = (pos1 >> 5); // Now determine bit number in arr[index] int bitNo1 = (pos1 & 0x1F); // Determine value of given bit number in // arr1[index1] return (arr1[index1] & (1 << bitNo1)) != 0; } // Used to set a bit at given position void set(int pos1){ // Determine index of bit position int index1 = (pos1 >> 5); // Used to set bit number in arr1[index1] int bitNo1 = (pos1 & 0x1F); arr1[index1] |= (1 << bitNo1); } //Shows main function to print all Duplicates void checkDuplicates1(int arr1[], int n1){ // Used to create a bit with 32000 bits BitArray ba1 = BitArray(320000); // Used to traverse array elements for (int i = 0; i < n1; i++){ // Shows index in bit array int num1 = arr1[i]; // Now if num is already present in bit array if (ba1.get(num1)) cout << num1 << " "; // Otherwise or else insert num else ba1.set(num1); } } }; // Driver code int main(){ int arr1[] = {2, 6, 2, 11, 13, 11}; int n1 = sizeof(arr1) / sizeof(arr1[0]); BitArray obj1 = BitArray(); obj1.checkDuplicates1(arr1, n1); return 0; }
আউটপুট
2 11