অনুপস্থিত পূর্ণসংখ্যার একটি প্রদত্ত অ্যারেতে অনুপস্থিত ধনাত্মক সংখ্যা খুঁজে পেতে জাভাতে একটি প্রোগ্রাম লিখুন

ধরা যাক আমরা সাজানো না হওয়া পূর্ণসংখ্যার একটি অ্যারে দিয়েছি। কাজটি হল ধনাত্মক অনুপস্থিত সংখ্যাটি খুঁজে বের করা যা প্রদত্ত অ্যারেতে [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

• এখন অনুপস্থিত নম্বর ফেরত দিন।

উদাহরণ

public class Solution {
   public static 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;
   }
   public static void main(String[] args){
      int arr[] = {0,4,2,1,6,3};
      int n = arr.length;
      int a=findMissingNumber(arr, n);
      System.out.println(a);
   }
}

আউটপুট

উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,

5

প্রদত্ত অ্যারেতে {0,4,2,1,6,3}, '5' অনুপস্থিত, এইভাবে আমরা 5 ফেরত দেব।