N සහ එහි ද්විත්ව පවතින ලීට්කෝඩ් විසඳුම තිබේදැයි පරීක්ෂා කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ගූගල්
අරා

ගැටළු ප්රකාශය

“N සහ එහි ද්විත්ව පැවැත්ම තිබේදැයි පරීක්ෂා කරන්න” යන ගැටලුවේදී අපට මූලද්‍රව්‍ය n මාලාවක් ලබා දී ඇත. අරාවෙහි දිග දෙකට වඩා වැඩි හෝ සමාන වේ.

අපගේ කර්තව්‍යය වන්නේ අරාවෙහි යුගලයක් තිබේදැයි පරීක්ෂා කිරීමයි, එනම් පළමු අගය දෙවන අගය මෙන් දෙගුණයක් වේ.

වඩාත් විධිමත් ලෙස i, j තිබේද යන්න පරීක්ෂා කර බැලිය යුතුය

උදාහරණයක්

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

පැහැදිලි කිරීම:

N සහ එහි ද්විත්ව පවතින ලීට්කෝඩ් විසඳුම තිබේදැයි පරීක්ෂා කරන්න

මෙම ආදානය සඳහා වන ප්‍රතිදානය සත්‍ය වන්නේ, ලබා දී ඇති අරාවෙහි කිසියම් අගයක් සහ එහි ද්විත්ව පිටවීමක් තිබේදැයි පරීක්ෂා කිරීමට ප්‍රශ්නය අපෙන් ඉල්ලා සිටින හෙයිනි, එබැවින් 7 සහ 14 මෙම නිර්ණායකයන් සපුරාලන්නේ 14 න් 7 ක් මෙන් දෙගුණයක් වන බැවිනි.

එන් සහ එහි ද්විත්ව පවතින ලීට්කෝඩ් විසඳුම තිබේදැයි පරීක්ෂා කිරීම සඳහා ප්‍රවේශය

මෙම ගැටළුව විසඳීම සඳහා පළමු ප්රවේශය වන්නේ තිරිසන් බලය ප්රවේශය. අරාවෙහි ඇති සෑම මූලද්‍රව්‍යයක් සඳහාම, අපි සම්පූර්ණ අරාව හරහා ගමන් කර එය දෙගුණයක් තිබේදැයි පරීක්ෂා කරමු. මෙම තත්වය තෘප්තිමත් කරන මූලද්‍රව්‍යයක් අපට හමු වුවහොත් අපි සත්‍යය වෙත ආපසු යමු. මෙම ප්‍රවේශය සඳහා කාල සංකීර්ණත්වය O (n * n) වන්නේ අරාවෙහි සෑම අංගයක් සඳහාම අපි සම්පූර්ණ අරාව හරහා ගමන් කරන බැවිනි.

අනුපිළිවෙලට නැති සිතියමක් හෝ ඇණවුම් නොකළ කට්ටලයක් භාවිතා කරමින් අපට මෙම ගැටළුව වඩා හොඳ කාල සංකීර්ණත්වයකින් විසඳා ගත හැකිය.

  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

N සහ එහි ද්විත්ව පැවැත්ම තිබේදැයි පරීක්ෂා කිරීම සඳහා ජාවා කේතය

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) ලෙස සෙවීමේ හා ඇතුළත් කිරීමේ සාමාන්‍ය කාල සංකීර්ණතාව සලකා බලයි.

අවකාශයේ සංකීර්ණතාව

ඉහත කේතයේ අවකාශය සංකීර්ණ වේ සාමාන්ය (n) නරකම අවස්ථාවක අපට සියලු අංග ගබඩා කිරීමට අවශ්‍ය විය හැකිය.

ආශ්රිත