समस्या विवरण
मान लीजिए हमारे पास असॉर्टेड पूर्णांकों की एक सरणी दी गई है। कार्य उस सकारात्मक लापता संख्या को ढूंढना है जो दी गई सरणी में [0 से n] की सीमा में मौजूद नहीं है।
उदाहरण
इनपुट-1
N = 9
arr = [0,2,5,9,1,7,4,3,6]आउटपुट
8व्याख्या - दी गई असॉर्टेड सरणी में, '8' एकमात्र सकारात्मक पूर्णांक है जो लापता है, इस प्रकार आउटपुट '8' है।
समस्या हल करने का दृष्टिकोण
इस विशेष समस्या को हल करने के कई दृष्टिकोण हैं। हालांकि, हम इस समस्या को रैखिक समय O(n) और कॉन्स्टेंट स्पेस O(1) में हल कर सकते हैं।
चूंकि हम जानते हैं कि हमारी सरणी आकार n की है और इसमें [0 से n] की सीमा में ठीक तत्व हैं। इसलिए, यदि हम प्रत्येक तत्व और उसके इंडेक्स के साथ 'n' का XOR ऑपरेशन करते हैं, तो हम परिणामी संख्या को एक अद्वितीय संख्या के रूप में ढूंढ सकते हैं जो सरणी से लापता है।
- [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आउटपुट
5दी गई सरणी {0,4,2,1,6,3} में, '5' लापता है, इस प्रकार हम 5 वापस करेंगे।