C++-এ অ্যারে থেকে একবার যেটি আছে সেই এলিমেন্ট বের করা (বাকিগুলো দুবার)

সমস্যা

একটি অ্যারে দেওয়া আছে যেখানে সব এলিমেন্ট ঠিক দুবার করে আছে, ছাড়া একটিই একবার আছে। সেটি খুঁজে বের করুন।

সমাধান: XOR অপারেশন

XOR-এর বৈশিষ্ট্য: a ^ a = 0, a ^ 0 = a। সব এলিমেন্ট XOR করলে ডুপ্লিকেটগুলো ক্যান্সেল হয়ে যাবে, শুধু যूनিক এলিমেন্ট বাকি থাকবে।

অ্যালগরিদম

1. res = 0।
2. প্রতিটি এলিমেন্ট e এর জন্য: res ^= e।
3. res রিটার্ন করুন।

C++ কোড

#include <bits/stdc++.h>
using namespace std;

int singleNumber(vector<int>& nums) {
    int ans = 0;
    for (int x : nums) ans ^= x;
    return ans;
}

int main() {
    vector<int> nums = {1,1,5,3,2,5,2};
    cout << singleNumber(nums); // 3
}

আউটপুট

3

কমপ্লেক্সিটি

• Time: O(n)
• Space: O(1)