N மற்றும் அதன் இரட்டை இருக்கும் லீட்கோட் தீர்வு இருக்கிறதா என்று சோதிக்கவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது கூகிள்
அணி

சிக்கல் அறிக்கை

சிக்கலில் ”N மற்றும் அதன் இரட்டை இருக்கிறதா என்று சரிபார்க்கவும்” எங்களுக்கு n கூறுகளின் வரிசை வழங்கப்படுகிறது. வரிசை நீளம் இரண்டை விட அதிகமாகவோ அல்லது சமமாகவோ இருக்கும்.

வரிசையில் ஒரு ஜோடி இருக்கிறதா என்று சோதிப்பதே எங்கள் பணி, அதாவது முதல் மதிப்பு இரண்டாவது மதிப்பை விட இருமடங்காகும்.

இன்னும் முறையாக i, j இருக்கிறதா என்று சோதிக்க வேண்டும்

உதாரணமாக

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

விளக்கம்:

N மற்றும் அதன் இரட்டை இருக்கும் லீட்கோட் தீர்வு இருக்கிறதா என்று சோதிக்கவும்

இந்த உள்ளீட்டிற்கான வெளியீடு உண்மைதான், ஏனெனில் கொடுக்கப்பட்ட வரிசையில் ஏதேனும் மதிப்பு மற்றும் அதன் இரட்டை வெளியேற்றம் இருக்கிறதா என்று சோதிக்க கேள்வி கேட்கிறது, எனவே 7 மற்றும் 14 இந்த அளவுகோல்களை திருப்தி செய்கின்றன, ஏனெனில் 14 என்பது 7 இன் இரட்டிப்பாகும்.

N மற்றும் அதன் இரட்டை இருக்கும் லீட்கோட் தீர்வு இருந்தால் சரிபார்க்க அணுகுமுறை

இந்த சிக்கலை தீர்க்க முதல் அணுகுமுறை முரட்டு சக்தி அணுகுமுறை. வரிசையில் உள்ள ஒவ்வொரு உறுப்புக்கும், முழுமையான வரிசையை கடந்து, அது இரட்டிப்பாக இருக்கிறதா என்று சோதிப்போம். இந்த நிலையை திருப்திப்படுத்தும் ஒரு உறுப்பு இருப்பதைக் கண்டால், நாங்கள் உண்மைக்குத் திரும்புவோம், இல்லையெனில், இறுதியில் பொய்யைத் திருப்புவோம். இந்த அணுகுமுறையின் நேர சிக்கலானது O (n * n) ஆகும், ஏனெனில் வரிசையின் ஒவ்வொரு உறுப்புக்கும் நாம் முழுமையான வரிசையை கடந்து செல்கிறோம்.

வரிசைப்படுத்தப்படாத வரைபடம் அல்லது வரிசைப்படுத்தப்படாத தொகுப்பைப் பயன்படுத்தி இந்த சிக்கலை சிறந்த நேர சிக்கலில் தீர்க்கலாம்.

  1. வரிசையை கடந்து செல்லுங்கள்.
  2. வரிசையில் உள்ள ஒவ்வொரு உறுப்புக்கும் இது இரட்டையா அல்லது அதன் பாதி ஏற்கனவே வரைபடமாக இருக்கிறதா என்று சரிபார்க்கவும்.
  3. நிபந்தனை உண்மையாக இருந்தால் உண்மையாகத் திரும்பவும், அந்த உறுப்பை வரைபடத்தில் சேர்க்கவும்.
  4. வரிசை டிராவல்ஸல் செய்யப்பட்டு, எந்த உறுப்புக்கும் இரட்டிப்பாக நாங்கள் காணவில்லை எனில், பொய்யைத் திருப்புக.

நடைமுறைப்படுத்தல்

N மற்றும் அதன் இரட்டை இருப்பு இருந்தால் சரிபார்க்க 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

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 மற்றும் அதன் இரட்டை லீட்கோட் தீர்வு இருந்தால் காசோலையின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

மேலே உள்ள குறியீட்டின் நேர சிக்கலானது ஓ (n) வரிசைப்படுத்தப்படாத வரைபடத்தில் O (1) என தேடுவதற்கும் செருகுவதற்கும் சராசரி நேர சிக்கலைக் கருத்தில் கொள்ளுங்கள்.

விண்வெளி சிக்கலானது

மேலே உள்ள குறியீட்டின் இட சிக்கலானது ஓ (n) ஏனெனில் மிக மோசமான நிலையில் நாம் எல்லா உறுப்புகளையும் சேமிக்க வேண்டியிருக்கும்.

குறிப்புகள்