জাভায় অনসোর্টেড ইন্টিজার অ্যারেতে অনুপস্থিত পজিটিভ নম্বর খুঁজে বের করা

একটি অনসোর্টেড ইন্টিজার অ্যারে দেওয়া থাকলে, ০ থেকে N পরিসরের মধ্যে কোন পজিটিভ নম্বরটি অনুপস্থিত সেটি খুঁজে বের করতে হবে।

ইনপুট-১: N = 9, arr = [0,2,5,9,1,7,4,3,6] → আউটপুট: 8

ইনপুট-২: N = 1, arr = [0] → আউটপুট: 1

সমাধানের পদ্ধতি (XOR পদ্ধতি)

O(n) টাইম এবং O(1) স্পেসে সমাধান করতে XOR অপারেশন ব্যবহার করা হয়। অ্যারেতে ০ থেকে N পর্যন্ত নম্বর থাকা উচিত, কিন্তু একটি নম্বর অনুপস্থিত। সব ইনডেক্স এবং এলিমেন্টের সাথে N কে XOR করলে অনুপস্থিত নম্বরটি পাওয়া যায়।

• অ্যারের সাইজ N এবং এলিমেন্টগুলো ইনপুট নিন।
• missing_no = N ইনিশিয়ালাইজ করুন।
• লুপ চালিয়ে missing_no ^= i ^ arr[i] করুন।
• শেষে missing_no রিটার্ন করুন।

জাভা কোড উদাহরণ

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 ans = findMissingNumber(arr, n);
        System.out.println(ans); // আউটপুট: 5
    }
}

আউটপুট

5

অ্যারে {0,4,2,1,6,3}-এ ৫ অনুপস্থিত, তাই ৫ রিটার্ন হয়।