పరిధి యొక్క తప్పిపోయిన అంశాలను కనుగొనండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Delhivery గ్రేఆరెంజ్ లింక్డ్ఇన్ నాగరో ఒపేరా Synopsys
హాష్ లార్సెన్ & టౌబ్రో సార్టింగ్

ఒక పరిధి యొక్క తప్పిపోయిన అంశాలను కనుగొనడంలో సమస్య ”మీకు ఇవ్వబడింది అమరిక ఒక నిర్దిష్ట పరిధిలోని విభిన్న మూలకాలు మరియు తక్కువ మరియు అధికంగా ఇవ్వబడిన పరిధి. శ్రేణిలో లేని పరిధిలో తప్పిపోయిన అన్ని అంశాలను కనుగొనండి. అవుట్పుట్ క్రమబద్ధీకరించబడిన క్రమంలో ఉండాలి.

ఉదాహరణ

పరిధి యొక్క తప్పిపోయిన అంశాలను కనుగొనండి

arr[] = [1, 3, 5, 7, 8, 9]

low=1 high = 10
2, 4, 6, 10

వివరణ

ఇవి తక్కువ మరియు అధికంగా ఇవ్వబడిన పరిధిలో శ్రేణిలో తప్పిపోయిన సంఖ్యలు, అంటే 1 మరియు 10.

arr[] = [2, 3, 7, 8]

low=1 high = 9
1, 4, 5, 6, 9

వివరణ

ఇవి తక్కువ మరియు అధికంగా ఇవ్వబడిన పరిధిలో శ్రేణిలో తప్పిపోయిన సంఖ్యలు, అంటే 1 మరియు 10.

అల్గారిథం

  1. ప్రకటించండి a సెట్.
  2. శ్రేణిలో ప్రయాణించి, అన్ని అంశాలను సెట్‌లో ఉంచండి.
  3. “నేను” తక్కువకు సమానం మరియు “నేను” అధికానికి సమానం కంటే తక్కువ.
    • ఒక సెట్‌లో “i” లేకపోతే.
      • 'నేను' ముద్రించండి.

వివరణ

శ్రేణిలో తప్పిపోయిన అన్ని అంశాలను ఇచ్చిన పరిధిలో తక్కువ మరియు అధికంగా కనుగొనమని అడిగే సమస్య స్టేట్‌మెంట్ మాకు ఇవ్వబడింది. దీన్ని పరిష్కరించడానికి మేము ఒక సమితిని ఉపయోగిస్తాము మరియు ఇచ్చిన శ్రేణి యొక్క సెట్లో విలువలను నిల్వ చేయబోతున్నాము. మాకు తక్కువ మరియు అధిక శ్రేణి ఇవ్వబడుతుంది, మేము అన్ని మూలకాలను తక్కువ మరియు అధికంగా కలుపుకొని ముద్రించాలి.

ఆ క్రమాన్ని పొందడానికి మేము ఇప్పటికే శ్రేణి మూలకాలను సెట్‌లో నిల్వ చేస్తాము. మేము 'i' ను తక్కువ స్థాయిలో ప్రారంభించే లూప్‌ను అమలు చేయాలి. 'i' విలువ అధికమయ్యే వరకు మేము లూప్‌ను నడుపుతాము. సెట్‌లో 'i' విలువ లేదా అని తనిఖీ చేసి, ఆపై 'i' ను ప్రింట్ చేయండి. అందువల్ల మేము ఇచ్చిన పరిధిలో శ్రేణి నుండి తప్పిపోయిన అన్ని అంశాలను పొందుతాము. ఒక ఉదాహరణను పరిశీలిద్దాం.

arr [] = {2, 3, 7, 8} low = 1, high = 9

మేము శ్రేణిని దాటాలి మరియు శ్రేణి యొక్క అన్ని అంశాలను సమితిలో ఉంచాలి. మా సెట్ అవుతుంది

సెట్ = [2,3,7,8]

ఒక లూప్‌లో i నుండి తక్కువ వరకు ప్రారంభించండి మరియు లూప్ ఎక్కువ వరకు నడుస్తుంది, దీని అర్థం 'i' తక్కువ = 1 మరియు అధిక = 9 కు సమానం

i = 1, సెట్‌లో i లేకపోతే, 1 ను ప్రింట్ చేస్తుంది

[1]

i = 2, సెట్ విలువ '2' కలిగి ఉంది మరియు ఏమీ చేయదు.

i = 3, సెట్ విలువ '3' కలిగి ఉంది మరియు ఏమీ చేయదు.

i = 4, సెట్‌లో i లేకపోతే, 4 ను ప్రింట్ చేస్తుంది

[1, 4]

i = 5, సెట్‌లో i లేకపోతే, 5 ను ప్రింట్ చేస్తుంది

[1, 4, 5]

i = 6, సెట్‌లో i లేకపోతే, 6 ను ప్రింట్ చేస్తుంది

[1, 4, 5, 6]

i = 7, సెట్ విలువ '7' కలిగి ఉంది మరియు ఏమీ చేయదు.

i = 8, సెట్ విలువ '8' కలిగి ఉంది మరియు ఏమీ చేయదు.

i = 9, సెట్‌లో i లేకపోతే, 1 ను ప్రింట్ చేస్తుంది

[1, 4, 5, 6, 9]

మా అవుట్పుట్ అవుతుంది: [1, 4, 5, 6, 9]

కోడ్

పరిధి యొక్క తప్పిపోయిన అంశాలను కనుగొనడానికి C ++ కోడ్

#include <unordered_set>
#include<iostream>

using namespace std;

void getMissingElements(int arr[], int n, int low, int high)
{
    unordered_set<int> myset;
    for (int i = 0; i < n; i++)
        myset.insert(arr[i]);

    for (int x = low; x <= high; x++)
        if (myset.find(x) == myset.end())
            cout << x << " ";
}
int main()
{
    int arr[] = { 2,3,7,8 };
    int low = 1, high = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    getMissingElements(arr, n, low, high);
    return 0;
}
1 4 5 6 9

పరిధి యొక్క తప్పిపోయిన అంశాలను కనుగొనడానికి జావా కోడ్

import java.util.HashSet;

class RangeMissingElements
{
    public static void getMissingElements(int arr[], int low, int high)
    {
        HashSet<Integer> myset = new HashSet<>();

        for (int i = 0; i < arr.length; i++)
        {
            myset.add(arr[i]);
        }

        for (int i = low; i <= high; i++)
        {
            if (!myset.contains(i))
            {
                System.out.print(i + " ");
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,7,8};
        int low = 1, high = 9;
        getMissingElements(arr, low, high);
    }
}
1 4 5 6 9

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (n + (అధిక-తక్కువ + 1))  (ఇక్కడ  “N” శ్రేణిలో ఉన్న మూలకాల సంఖ్య, "అధిక" మరియు “తక్కువ” అందించిన ఇన్పుట్.

అంతరిక్ష సంక్లిష్టత

పై), చెత్త సందర్భంలో, అన్ని అంశాలు విభిన్నంగా ఉంటే. మేము అన్ని అంశాలను నిల్వ చేయాలి. అందువల్ల అల్గోరిథం చేయడానికి సరళ సమయం అవసరం.