কনসেপ্ট
n সংখ্যক উপাদানের অ্যারে (n ≤ 32,000) দেওয়া আছে। ডুপ্লিকেট উপাদানগুলো প্রিন্ট করতে হবে। মেমোরি সীমা: ৪ কিলোবাইট (৩২,০০০ বিট)।
ইনপুট ১
arr[] = {2, 6, 2, 11, 13, 11}
আউটপুট ১
2 11
ইনপুট ২
arr[] = {60, 50, 60}
আউটপুট ২
60
পদ্ধতি
৪ KB = ৩২,৭৬৮ বিট > ৩২,০০০। বিট ভেক্টর (bit vector) বানান যেখানে প্রতিটি বিট একটি ইন্টিজার রিপ্রেজেন্ট করে। অ্যারে ট্রাভার্স করুন: উপাদান v-এর জন্য বিট v চেক করুন। সেট থাকলে ডুপ্লিকেট, প্রিন্ট করুন। নয় তবে সেট করুন।
উদাহরণ (C++ কোড)
// C++: বিট অ্যারে দিয়ে ডুপ্লিকেট খুঁজে বের
#include <bits/stdc++.h>
using namespace std;
class BitArray {
int *arr1;
public:
BitArray() {}
BitArray(int n1) { arr1 = new int[(n1>>5)+1]; } // ৩২ বিটต่อ ইন্ট
bool get(int pos1) {
int index1 = pos1>>5, bitNo1 = pos1&0x1F;
return (arr1[index1] & (1<>5, bitNo1 = pos1&0x1F;
arr1[index1] |= (1<
আউটপুট
2 11
