क्रमबद्ध पूर्णांकों के दिए गए सरणी में लापता धनात्मक संख्या को खोजने के लिए जावा में एक प्रोग्राम लिखें

मान लीजिए कि हमने बिना क्रमित पूर्णांकों की एक सरणी दी है। कार्य सकारात्मक लापता संख्या को खोजने के लिए है जो दिए गए सरणी में [0 से n] की सीमा में मौजूद नहीं है। उदाहरण के लिए,

इनपुट-1 -

N = 9
arr = [0,2,5,9,1,7,4,3,6]

आउटपुट -

8

स्पष्टीकरण - दिए गए क्रमबद्ध सरणी में, '8' एकमात्र धनात्मक पूर्णांक है जो गायब है, इस प्रकार आउटपुट '8' है।

इनपुट-2 -

N = 1
arr = [0]

आउटपुट -

1

स्पष्टीकरण - दिए गए सरणी में, '1' एकमात्र सकारात्मक पूर्णांक है जो गायब है, इस प्रकार आउटपुट '1' है।

इस समस्या को हल करने का तरीका

इस विशेष समस्या को हल करने के लिए कई दृष्टिकोण हैं। हालाँकि, हम इस समस्या को रैखिक समय O(n) और स्थिर स्थान O(1) में हल कर सकते हैं।

चूंकि हम जानते हैं कि हमारी सरणी आकार n की है और इसमें [0 से n] की सीमा में बिल्कुल तत्व शामिल हैं। इसलिए, यदि हम 'n' के साथ प्रत्येक तत्व और उसके सूचकांक का XOR संचालन करते हैं, तो हम परिणामी संख्या को एक अद्वितीय संख्या के रूप में पा सकते हैं जो सरणी से गायब है।

• [0 से n] की श्रेणी में तत्वों के साथ सरणी के एन आकार का इनपुट लें।

• एक पूर्णांक फ़ंक्शन findMissingNumber(int arr[], int size) इनपुट के रूप में एक सरणी और उसका आकार लेता है और लापता संख्या देता है।

• आइए n लें XOR ऑपरेशन करने के लिए एक लापता नंबर के रूप में।

• सभी सरणी तत्वों पर पुनरावृति करें और लापता संख्या, यानी, n के संबंध में प्रत्येक सरणी तत्व और उसके अनुक्रमित के साथ XOR संचालन करें।

• अब लापता नंबर लौटाएं।

उदाहरण

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 a=findMissingNumber(arr, n);
      System.out.println(a);
   }
}

आउटपुट

उपरोक्त कोड को चलाने से आउटपुट इस प्रकार उत्पन्न होगा,

5

दिए गए सरणी में {0,4,2,1,6,3}, '5' गायब है, इस प्रकार हम 5 वापस आ जाएंगे।