এন এবং এর ডাবল লেটকোড সমাধান রয়েছে কিনা তা পরীক্ষা করে দেখুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় গুগল
বিন্যাস

সমস্যা বিবৃতি

"এন এবং এর ডাবল অস্তিত্ব পরীক্ষা করুন" সমস্যাটিতে আমাদের এন উপাদানগুলির একটি অ্যারে দেওয়া হয়। অ্যারের দৈর্ঘ্য দুটি থেকে বড় বা সমান।

আমাদের কাজটি অ্যারেতে এমন কোনও জুড়ি রয়েছে কিনা তা পরীক্ষা করা হয় যে প্রথম মান দ্বিতীয় মানের দ্বিগুণ double

আরও আনুষ্ঠানিকভাবে আমাদের যাচাই করা দরকার যে আমি, জে আছে যার জন্য আমি রয়েছি

উদাহরণ

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

ব্যাখ্যা:

এন এবং এর ডাবল লেটকোড সমাধান রয়েছে কিনা তা পরীক্ষা করে দেখুন

এই ইনপুটটির আউটপুটটি সত্য কারণ প্রশ্নটি আমাদের প্রদত্ত অ্যারেতে কোনও মান এবং এর দ্বিগুণ প্রস্থান কিনা তা পরীক্ষা করে দেখতে বলে, সুতরাং 7 এবং 14 এই মানদণ্ডকে 14 হিসাবে সন্তুষ্ট করে কারণ 7 এর পরিমাণ XNUMX এর দ্বিগুণ।

এন এবং এর ডাবল বিদ্যমান লেটকোড সমাধানের জন্য কিনা তা পরীক্ষা করার জন্য অ্যাপ্রোচ

এই সমস্যাটি সমাধানের প্রথম পদ্ধতির নাম পাশবিক বল পন্থা অ্যারের প্রতিটি উপাদানগুলির জন্য, আমরা সম্পূর্ণ অ্যারেটি অতিক্রম করব এবং এটি দ্বিগুণ রয়েছে কিনা তা পরীক্ষা করব। যদি আমরা এই শর্তটিকে সন্তুষ্ট করার মতো কোনও উপাদান খুঁজে পাই তবে আমরা সত্যটিতে ফিরে আসব, অন্যথায়, আমরা শেষ পর্যন্ত মিথ্যাতে ফিরে আসব। এই পদ্ধতির জন্য সময় জটিলতা হ'ল ও (এন * এন) কারণ অ্যারের প্রতিটি উপাদানগুলির জন্য আমরা সম্পূর্ণ অ্যারেটি অনুসরণ করছি।

আনর্ডারড ম্যাপ বা আনর্ডারড সেট ব্যবহার না করে আমরা আরও ভাল সময়ের জটিলতায় এই সমস্যাটি সমাধান করতে পারি।

  1. অ্যারে অতিক্রম করুন।
  2. অ্যারের প্রতিটি উপাদানগুলির জন্য এটি দ্বিগুণ বা এর অর্ধেক ইতিমধ্যে এটি ম্যাপে উপস্থিত রয়েছে কিনা তা পরীক্ষা করে দেখুন।
  3. যদি শর্তটি সত্য হয় তবে কেবল সত্যটি ফিরে আসুন অন্যথায় সেই উপাদানটিকে মানচিত্রে যুক্ত করুন।
  4. যদি অ্যারে ট্র্যাভারসাল হয়ে যায় এবং আমরা কোনও উপাদান দ্বিগুণ খুঁজে পাই না, তবে মিথ্যা ফিরিয়ে দিন।

বাস্তবায়ন

সি ++ কোড যদি চেক এর জন্য এন এবং এর ডাবল বিদ্যমান থাকে

#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) হিসাবে সন্ধান এবং সন্নিবেশ করার গড় সময়ের জটিলতা বিবেচনা করুন।

স্থান জটিলতা

উপরের কোডটির স্পেস জটিলতা উপর) কারণ সবচেয়ে খারাপ ক্ষেত্রে আমাদের সমস্ত উপাদানগুলি সংরক্ষণ করার প্রয়োজন হতে পারে।

তথ্যসূত্র