একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে যেখানে শুধু একটি সংখ্যা বিজোড় বার (odd number of times) উপস্থিত আছে, বাকি সব সংখ্যা জোড় বার উপস্থিত আছে। সেই বিজোড় বার উপস্থিত সংখ্যাটি খুঁজে বের করতে হবে।
অ্যাপরোচ: অ্যারেটি সোর্ট করলে একই সংখ্যাগুলো একসাথে আঁকবয়ে যাবে। তারপর ইটারেট করে বিজোড় কাউন্ট ਵਾਲা উপাদানটি খুঁজে বের করা যাবে।
উদাহরণ কোড
const arr = [20, 1, -1, 2, -2, 3, 3, 5, 5, 1, 2, 4, 20, 4, -1, -2, 5];
const findOdd = arr => {
let count = 0;
let last;
arr.sort((a, b) => a - b);
for (let i = 0; i < arr.length; i++) {
if (arr[i] === last) {
count++;
continue;
}
if (count % 2) {
return last;
}
last = arr[i];
count = 1;
}
return last;
};
console.log(findOdd(arr));
আউটপুট
5
ব্যাখ্যা
arr.sort((a, b) => a - b)দিয়ে সংখ্যাগুলো আরোহী ক্রমে সাজানো হয়েছে।lastভেরিয়েবলটি বর্তমান ट्र্যাক করা সংখ্যা,countতার ফ্রিকোয়েন্সি।- যখন নতুন সংখ্যা আসে, আগের সংখ্যার
countবিজোড় কিনা চেক করা হয়। বিজোড় হলে সেটি রিটার্ন করা হয়। - লুপ শেষ হলে
lastরিটার্ন করা হয় (শেষ সংখ্যাটি যদি বিজোড় বার থাকে)।
অপ্টিমাইজড বিকল্প (XOR ব্যবহার করে)
XOR অপারেশন ব্যবহার করে O(n) টাইম এবং O(1) স্পেসে সমাধান সম্ভব:
const findOddXOR = arr => arr.reduce((a, b) => a ^ b, 0);
console.log(findOddXOR(arr)); // 5
কারণ: x ^ x = 0 এবং x ^ 0 = x। জোড় বার থাকা সংখ্যাগুলো XOR দিয়ে ০ হয়ে যাবে, শুধু বিজোড় বার থাকা সংখ্যাটি অবশিষ্ট থাকবে।
