अगर एन और इसके डबल एक्जिट लेकोडकोड समाधान की जाँच करें


कठिनाई स्तर आसान
में अक्सर पूछा गूगल
ऐरे

समस्या का विवरण

समस्या में "एन और उसके दोहरे अस्तित्व की जाँच करें" हमें एन तत्वों की एक सरणी दी जाती है। ऐरे की लंबाई दो से अधिक या उसके बराबर है।

हमारा कार्य यह जांचना है कि क्या सरणी में कोई जोड़ी मौजूद है जैसे कि पहला मूल्य दूसरा मूल्य है।

औपचारिक रूप से हमें यह जांचने की आवश्यकता है कि क्या मौजूद है i, j जिसके लिए मैं

उदाहरण

arr = [7,1,14,11]
true

स्पष्टीकरण:

अगर एन और इसके डबल एक्जिट लेकोडकोड समाधान की जाँच करें

इस इनपुट के लिए आउटपुट सही है क्योंकि सवाल हमें यह जांचने के लिए कहता है कि क्या दिए गए एरे में कोई वैल्यू और इसका डबल एग्जिट है, इसलिए 7 और 14 इन मानदंडों को संतुष्ट करते हैं क्योंकि 14 7 का डबल है।

जांच के लिए दृष्टिकोण यदि एन और इसके डबल एक्ज़िट लेकोडकोड समाधान

इस समस्या को हल करने के लिए पहला दृष्टिकोण है जानवर बल दृष्टिकोण। सरणी में प्रत्येक तत्व के लिए, हम पूर्ण सरणी को पीछे छोड़ेंगे और जांचेंगे कि क्या यह मौजूद है। यदि हम इस स्थिति को संतुष्ट करने वाला तत्व पाते हैं, तो हम सही लौटेंगे, अन्यथा, हम अंत में झूठे वापस आ जाएंगे। इस दृष्टिकोण के लिए समय की जटिलता हे (n * n) है क्योंकि सरणी के प्रत्येक तत्व के लिए हम पूर्ण सरणी का पता लगा रहे हैं।

हम इस समस्या को एक बेहतर समय जटिलता में एक अनियंत्रित मानचित्र या अनियंत्रित सेट का उपयोग करके हल कर सकते हैं।

  1. सरणी को पीछे छोड़ें।
  2. सरणी में प्रत्येक तत्व के लिए जाँच करें कि यह डबल है या इसका आधा पहले से ही मौजूद है या नहीं।
  3. अगर हालत सही है तो बस सच लौटें और उस तत्व को नक्शे में जोड़ें।
  4. यदि सरणी ट्रैवर्सल किया गया है और हमें किसी भी तत्व का दोगुना नहीं मिला है, तो गलत लौटें।

कार्यान्वयन

चेक + एन और उसके डबल एक्जिस्ट के लिए C ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
    bool checkIfExist(vector<int>& arr) {
      unordered_map<int,bool>mp;
        for(int i=0;i<arr.size();i++)
        {
            if(mp[arr[i]*2]==1||(mp[arr[i]/2]==1&&arr[i]%2==0))
                return true;
            mp[arr[i]]=1;
        }
        return false;
    }
int main() 
{ 
 vector<int> arr = {7,1,14,11}; 
 bool ans=checkIfExist(arr);
 cout <<boolalpha;
 cout<<ans<<endl;
 return 0;
}
true

चेक कोड के लिए जावा कोड यदि एन और इसका डबल एक्जिस्ट

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static boolean checkIfExist(int[] arr) {
        Set<Integer> seen = new HashSet<>();   
        for (int i : arr) {
            if (seen.contains(2 * i) || (i % 2 == 0 && seen.contains(i / 2)))
                return true;
            seen.add(i);
        }
        return false;
    }
  public static void main(String[] args) {
        int [] arr = {7,1,14,11}; 
        boolean ans=checkIfExist(arr); 
        System.out.println(ans);
  }
}
true

जांच की जटिलता विश्लेषण अगर एन और इसके डबल एक्ज़िस्ट लेटकोड सॉल्यूशन

समय की जटिलता

उपरोक्त कोड की समय जटिलता है पर) ओ (1) के रूप में एक अव्यवस्थित नक्शे में खोज और सम्मिलित करने की औसत समय जटिलता पर विचार करना।

अंतरिक्ष की जटिलता

उपरोक्त कोड की अंतरिक्ष जटिलता है पर) क्योंकि सबसे खराब स्थिति में हमें सभी तत्वों को संग्रहीत करने की आवश्यकता हो सकती है।

संदर्भ