একটি আনসর্টেড পূর্ণসংখ্যা অ্যারে দেওয়া থাকলে, [0, n] রেঞ্জে কোন পজিটিভ সংখ্যা অনুপস্থিত সেটা বের করতে হবে।
ইনপুট-১
N = 9, arr = [0,2,5,9,1,7,4,3,6]
আউটপুট
8
ইনপুট-২
N = 1, arr = [0]
আউটপুট
1
সমাধানের পদ্ধতি
XOR অপারেশন ব্যবহার করে O(n) টাইম এবং O(1) স্পেসে সমাধান করা যায়।
- অ্যারে সাইজ N এবং এলিমেন্ট ইনপুট নিন।
findMissingNumber(int arr[], int size)ফাংশন মিসিং নাম্বার রিটার্ন করবে।missing_no = sizeদিয়ে শুরু করুন।- প্রতিটি ইন্ডেক্স i এবং এলিমেন্ট arr[i]-র সাথে XOR করুন:
missing_no ^= i ^ arr[i]। - শেষে
missing_noহবে মিসিং সংখ্যাটি।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int findMissingNumber(int *arr, int size) {
int missing_no = size;
for (int i = 0; i < size; i++)
missing_no ^= i ^ arr[i];
return missing_no;
}
int main() {
int n = 6;
int arr[n] = {0,4,2,1,6,3};
cout << findMissingNumber(arr, n) << endl;
return 0;
}
আউটপুট
5
