C++-এ 1 থেকে N পর্যন্ত উপাদান থাকা অ্যারেতে চারটি অনুপস্থিত সংখ্যা খুঁজে বের করা

কনসেপ্ট

অনন্য পূর্ণসংখ্যার অ্যারে দেওয়া আছে যেগুলো 1 থেকে N-এর মধ্যে। অ্যারের আকার (N-4) এবং কোনো উপাদান রিপিট হয়নি। অর্থাৎ ১ থেকে N পর্যন্ত চারটি সংখ্যা অনুপস্থিত। সেগুলো সর্টেড আকারে খুঁজে বের করুন।

ইনপুট ১

arr[] = {3, 6, 7, 4, 10}

আউটপুট ১

1 2 5 8 9

ইনপুট ২

arr[] = {2, 8, 4, 13, 6, 11, 9, 5, 10}

আউটপুট ২

1 3 7 12

পদ্ধতি

O(N) সহজ সমাধান: O(N) অক্সিলিয়ারি স্পেস দিয়ে ভিজিটেড মার্ক করুন।

O(1) অক্সিলিয়ারি স্পেস সমাধান: ৪টি উপাদানের helper অ্যারে নিন। ইনপুট অ্যারে ট্রাভার্স করুন: abs(arr[i]) <= n হলে arr[abs(arr[i])-1] *= -1 করুন (নেগেটিভ করে মার্ক)। abs(arr[i]) > n হলে helper[abs(arr[i])%n - 1] = -1 করুন। শেষে পজিটিভ ভ্যালু থাকা ইনডেক্সগুলো +1 এবং helper-এ পজিটিভ থাকা ইনডেক্সগুলো + n + 1 প্রিন্ট করুন।

উদাহরণ (C++ কোড)

// CPP: ৪টি অনুপস্থিত সংখ্যা O(N) টাইম O(1) স্পেসে
#include <bits/stdc++.h>
using namespace std;

void missing4(int arr1[], int n1) {
    int helper[4] = {0};
    for (int i=0; i 0) cout << (i+1) << " ";
    for (int i=0; i<4; i++) if (helper[i] >= 0) cout << (n1 + i + 1) << " ";
}

int main() {
    int arr1[] = {2,8,4,13,6,11,9,5,10};
    int n1 = sizeof(arr1)/sizeof(arr1[0]);
    missing4(arr1, n1);
    return 0;
}

আউটপুট

1 3 7 12