এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে যার সাইজ n। আমাদের কাজ হল রেঞ্জ থেকে একমাত্র মিসিং নাম্বার বের করা।
অ্যারেটি সবচেয়ে ছোট মান থেকে (সর্বোচ্চ + n) পর্যন্ত সব মান ধারণ করে। রেঞ্জের একটি এলিমেন্ট অ্যারেতে মিসিং। সেটি বের করতে হবে।
উদাহরণ দেখি:
ইনপুট
arr[] = {4, 8, 5, 7}
আউটপুট
6
সমাধানের পদ্ধতি
একটি সহজ পদ্ধতি হল অ্যারে সর্ট করে রেঞ্জের প্রথম এলিমেন্ট খুঁজে বের করা যা অ্যারেতে নেই কিন্তু রেঞ্জে আছে।
এই সমাধান O(n log n) টাইম নেয়। আরও দক্ষ পদ্ধতি হল XOR ব্যবহার করা। রেঞ্জের সব ভ্যালুর XOR এবং অ্যারের সব ভ্যালুর XOR বের করুন। এই দুটি XOR-এর XOR হবে মিসিং ভ্যালু।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int findMissingNumArr(int arr[], int n){ int arrMin = *min_element(arr, arr+n); int numXor = 0; int rangeXor = arrMin; for (int i = 0; i < n; i++) { numXor ^= arr[i]; arrMin++; rangeXor ^= arrMin; } return numXor ^ rangeXor; } int main(){ int arr[] = { 5, 7, 4, 8, 9}; int n = sizeof(arr)/sizeof(arr[0]); cout<<"The missing value in the array is "<<findMissingNumArr(arr, n); return 0; }
আউটপুট
The missing value in the array is 6
