ধারণা
অনন্য পূর্ণসংখ্যার একটি প্রদত্ত অ্যারের ক্ষেত্রে যেখানে প্রদত্ত অ্যারের প্রতিটি পূর্ণসংখ্যা সীমা [1, N] এর মধ্যে থাকে, অ্যারের আকার (N-4) এবং কোনো একক উপাদান পুনরাবৃত্তি হয় না। সুতরাং, চারটি সংখ্যা, 1 থেকে এন, অ্যারেতে অনুপস্থিত। সাজানো ক্রমে 4টি অনুপস্থিত সংখ্যা নির্ধারণ করুন।
ইনপুট
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) সমাধান হল পরিদর্শন করা উপাদানগুলি নির্দেশ করতে বা চিহ্নিত করার জন্য N আকারের একটি সহায়ক অ্যারে বাস্তবায়ন করা। ইনপুট অ্যারেতে যান এবং অক্জিলিয়ারী অ্যারেতে উপাদানগুলি নির্দেশ করুন বা চিহ্নিত করুন। শেষ পর্যন্ত সেই সমস্ত সূচী প্রিন্ট করুন যেগুলি নির্দেশিত বা চিহ্নিত করা হয়নি।
এখন প্রশ্ন উঠছে কিভাবে O(1) অক্সিলিয়ারি স্পেস দিয়ে সমাধান করা যায়?
প্রথমে আমরা 4টি অনুপস্থিত সংখ্যার ক্ষতিপূরণ দেওয়ার জন্য দৈর্ঘ্য 4-এর সাহায্যকারী নামে একটি অ্যারে শুরু করি এবং তাদের শূন্য দিয়ে পূরণ করি। এর পরে আমরা প্রদত্ত অ্যারের i=0 থেকে i
এটি দেখা গেছে যে যদি উপাদানটির পরম মান ইনপুটারের দৈর্ঘ্যের চেয়ে ছোট হয় তবে আমরা অ্যারে[temp] উপাদানটিকে -1 দিয়ে গুণ করব (ভিজিট করা উপাদানটিকে নির্দেশ করতে বা চিহ্নিত করার জন্য)।
এটি দেখা গেছে যে যদি উপাদানটির পরম মান ইনপুটারের দৈর্ঘ্যের চেয়ে বড় হয় তবে আমরা সহায়ক [temp%array.length] উপাদানটির মান -1 দিয়ে রাখব (ভিজিট করা উপাদানটি নির্দেশ করতে বা চিহ্নিত করার জন্য)।
এখন আমরা ইনপুট অ্যারে এবং যে সূচীগুলির মান এখনও শূন্যের চেয়ে বড় সেগুলির উপর পুনরাবৃত্তি করি তখন সেই উপাদানগুলি ইনপুট অ্যারেতে দেখা যায়নি। এর ফলস্বরূপ আমরা সূচীর (সূচি+1) মান প্রিন্ট করি যার উপাদান শূন্যের চেয়ে বড়।
এখন আমরা হেল্পার অ্যারে এবং সেই সূচকগুলির উপর পুনরাবৃত্তি করব যার মান এখনও শূন্যের চেয়ে বড় তখন সেই উপাদানগুলি ইনপুট অ্যারেতে দেখা যায়নি। এর ফলে আমরা সূচকের (index+array.length+1) মান মুদ্রণ করি যার উপাদান শূন্যের চেয়ে বড়।
উদাহরণ
// CPP program to find missing 4 elements
// in an array of size N where elements are
// in range from 1 to N+4.
#include <bits/stdc++.h>
using namespace std;
// Used to find missing 4 numbers in O(N) time
// and O(1) auxiliary space.
void missing4(int arr1[], int n1){
// Used to keep track of 4 possible numbers
// greater than length of input array
// In case of Java, helper is automatically
// initialized as 0.
int helper[4];
// Visit the input array and mark
// visited elements either by marking
// them as negative in arr[] or in
// helper[].
for (int i = 0; i < n1; i++) {
int temp1 = abs(arr1[i]);
// It has been seen that if element is smaller than or
// equal to length, mark its
// presence in arr1[]
if (temp1 <= n1)
arr1[temp1 - 1] *= (-1);
// Indicate or mark presence in helper[]
else if (temp1 > n1) {
if (temp1 % n1 != 0)
helper[temp1 % n1 - 1] = -1;
else
helper[(temp1 % n1) + n1 - 1] = -1;
}
}
// Used to print all those elements whose presence
// is not marked.
for (int i = 0; i < n1; i++)
if (arr1[i] > 0)
cout << (i + 1) << " ";
for (int i = 0; i < 4; i++)
if (helper[i] >= 0)
cout << (n1 + i + 1) << " ";
return;
}
// Driver code
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
