ধরা যাক আমরা সাজানো না হওয়া পূর্ণসংখ্যার একটি অ্যারে দিয়েছি। কাজটি হল ধনাত্মক অনুপস্থিত সংখ্যাটি খুঁজে বের করা যা প্রদত্ত অ্যারেতে [0 থেকে n] পরিসরে উপস্থিত নয়। উদাহরণস্বরূপ,
ইনপুট-1 −
N = 9 arr = [0,2,5,9,1,7,4,3,6]
আউটপুট −
8
ব্যাখ্যা − প্রদত্ত সাজানো বিন্যাসে, '8' হল একমাত্র ধনাত্মক পূর্ণসংখ্যা যা অনুপস্থিত, এইভাবে আউটপুট হল '8'৷
ইনপুট-2 −
>N= 1 arr= [0]
আউটপুট −
1
ব্যাখ্যা − প্রদত্ত অ্যারেতে, '1' হল একমাত্র ধনাত্মক পূর্ণসংখ্যা যা অনুপস্থিত, এইভাবে আউটপুট হল '1'৷
এই সমস্যা সমাধানের পদ্ধতি
এই বিশেষ সমস্যা সমাধানের জন্য বিভিন্ন পন্থা আছে। যাইহোক, আমরা এই সমস্যার সমাধান করতে পারি রৈখিক সময় O(n) এবং ধ্রুবক স্থান O(1).
যেহেতু আমরা জানি যে আমাদের অ্যারেটি n আকারের এবং এতে [0 থেকে n] রেঞ্জের মধ্যে ঠিক উপাদান রয়েছে। তাই আমরা যদি প্রতিটি উপাদানের XOR অপারেশন করি এবং 'n' দিয়ে এর সূচী করি, তাহলে আমরা ফলাফল সংখ্যাটিকে একটি অনন্য সংখ্যা হিসাবে খুঁজে পেতে পারি যা অ্যারে থেকে অনুপস্থিত৷
-
[0 থেকে n] পরিসরে উপাদান সহ অ্যারের N আকারের ইনপুট নিন।
-
একটি পূর্ণসংখ্যা ফাংশন findMissingNumber(int arr[], int size) একটি অ্যারে এবং এর আকারকে ইনপুট হিসাবে নেয় এবং অনুপস্থিত সংখ্যা প্রদান করে।
-
চলুন n নেওয়া যাক XOR অপারেশন করার জন্য একটি অনুপস্থিত সংখ্যা হিসাবে।
-
সমস্ত অ্যারের উপাদানগুলির উপর পুনরাবৃত্তি করুন এবং অনুপস্থিত সংখ্যার ক্ষেত্রে প্রতিটি অ্যারের উপাদান এবং এর সূচীগুলির সাথে XOR অপারেশন সম্পাদন করুন, যেমন, n .
-
এখন অনুপস্থিত নম্বর ফেরত দিন।
উদাহরণ
#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
যদি আমরা অ্যারের প্রতিটি উপাদান এবং এর সূচীগুলির সাথে XOR অপারেশন করি তবে এটি '5' মুদ্রণ করবে যা অ্যারে থেকে অনুপস্থিত৷
