چیک کریں کہ آیا N اور اس کا ڈبل ​​موجود لیٹکوڈ حل ہے


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے گوگل
لڑی

مسئلہ یہ بیان

اس مسئلے میں "چیک کریں کہ کیا N اور اس کا ڈبل ​​موجود ہے" میں ہمیں n عناصر کی ایک صف دی جاتی ہے۔ صف کی لمبائی دو سے زیادہ یا اس کے برابر ہے۔

ہمارا کام یہ چیک کرنا ہے کہ کیا صف میں کوئی جوڑی موجود ہے کہ پہلی قدر دوسری قیمت سے دوگنی ہے۔

مزید باضابطہ طور پر ہمیں یہ چیک کرنے کی ضرورت ہے کہ آیا میں ، ج ، موجود ہے یا نہیں

مثال کے طور پر

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

وضاحت:

چیک کریں کہ آیا N اور اس کا ڈبل ​​موجود لیٹکوڈ حل ہے

اس ان پٹ کے لئے آؤٹ پٹ درست ہے کیونکہ سوال ہم سے یہ پوچھنے کے لئے کہتا ہے کہ آیا دیئے گئے صف میں کوئی قدر اور اس کا ڈبل ​​خارج ہوجاتا ہے ، لہذا 7 اور 14 ان معیارات کو پورا کرتا ہے کیونکہ 14 7 کا دوگنا ہے۔

اگر ن اور اس کا ڈبل ​​موجود لیٹ کوڈ حل کی جانچ پڑتال کے ل Appro اپروچ کریں

اس مسئلے کو حل کرنے کا پہلا نقطہ نظر ہے جسمانی طاقت نقطہ نظر صف میں موجود ہر عنصر کے ل we ، ہم مکمل صف کو عبور کریں گے اور چیک کریں گے کہ آیا یہ ڈبل موجود ہے یا نہیں۔ اگر ہمیں کوئی عنصر اس حالت سے مطمئن نظر آتا ہے تو ہم سچ میں واپس آجائیں گے ، بصورت دیگر ، ہم آخر میں باطل لوٹ آئیں گے۔ اس نقطہ نظر کے لئے وقت کی پیچیدگی O (n * n) ہے کیونکہ صف کے ہر عنصر کے لئے ہم مکمل صف کو عبور کررہے ہیں۔

ہم غیر منظم نقشہ یا غیر ترتیب شدہ سیٹ کا استعمال کرکے بہتر وقت کی پیچیدگی میں اس مسئلے کو حل کر سکتے ہیں۔

  1. صف کو عبور کریں۔
  2. صف میں موجود ہر عنصر کے ل check اگر یہ ڈبل ہے یا اس کا آدھا نقشہ موجود ہے۔
  3. اگر حالت درست ہے تو بس صحیح واپس آجائیں ورنہ اس عنصر کو نقشہ میں شامل کریں۔
  4. اگر سرنی ٹراورسال ہوچکی ہے اور ہمیں کسی بھی عنصر سے دوگنا نہیں ملا ، تو غلط کو لوٹائیں۔

عمل

C ++ کوڈ اگر چیک N اور اس کا ڈبل ​​موجود ہے

#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

جانچ پڑتال کا پیچیدہ تجزیہ اگر N اور اس کا ڈبل ​​لیٹ کوڈ حل موجود ہے

وقت کی پیچیدگی

مذکورہ کوڈ کی ٹائم پیچیدگی ہے اے (ن) غیر منظم نقشہ میں O (1) کی طرح تلاش اور داخل کرنے کی اوسط وقت کی پیچیدگی پر غور کرنا۔

خلائی پیچیدگی

مذکورہ کوڈ کی جگہ کی پیچیدگی ہے اے (ن) کیونکہ خراب صورتحال میں ہمیں تمام عناصر کو ذخیرہ کرنے کی ضرورت پڑسکتی ہے۔

حوالہ جات