अवधारणा
अद्वितीय पूर्णांकों के दिए गए सरणी के संबंध में जहां दिए गए सरणी का प्रत्येक पूर्णांक श्रेणी [1, N] में स्थित है, सरणी का आकार (N-4) है और कोई एकल तत्व दोहराया नहीं जाता है। तो, सरणी में 1 से N तक की चार संख्याएँ गायब हैं। 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(1) सहायक स्थान से कैसे हल किया जाए?
सबसे पहले हम 4 लापता संख्याओं की भरपाई करने और उन्हें शून्य से भरने के लिए लंबाई 4 के सहायक नामक एक सरणी को प्रारंभ करते हैं। उसके बाद हम दिए गए सरणी के i =0 से i
यह देखा गया है कि यदि तत्व का निरपेक्ष मान इनपुट सरणी की लंबाई से छोटा है तो हम सरणी [अस्थायी] तत्व को -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