ఇచ్చిన పరిధిలోని విలువలతో శ్రేణి మూలకాల గణన కోసం ప్రశ్నలు


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది Coursera డిఇ షా గూగుల్ PayU స్నాప్డీల్ టైమ్స్ ఇంటర్నెట్ యాహూ
అర్రే బిట్స్ ప్రశ్న సమస్య

సమస్యల నివేదిక

“ఇచ్చిన పరిధిలో విలువలతో శ్రేణి మూలకాల గణనల కోసం ప్రశ్నలు” అనే సమస్య మీకు ఉందని పేర్కొంది పూర్ణ సంఖ్య అమరిక మరియు రెండు సంఖ్య x మరియు y. ఇచ్చిన x మరియు y ల మధ్య ఉన్న శ్రేణిలో ఉన్న సంఖ్యల సంఖ్యను తెలుసుకోవడానికి సమస్య ప్రకటన అడుగుతుంది.

ఉదాహరణ

arr[]={2,4,6,8,1,10}
x = 2, y = 8
4

వివరణ

ఎందుకంటే శ్రేణిలో 4 అంశాలు ఉన్నాయి, అంటే 2, 4, 6 మరియు 8 లు 2 మరియు 8 మధ్య ఉంటాయి.

ఇచ్చిన పరిధిలోని విలువలతో శ్రేణి మూలకాల గణన కోసం ప్రశ్నలు

arr[]={2,4,6,8,1,10}
x = 5, y = 10
3

వివరణ

ఎందుకంటే శ్రేణిలో 3 అంశాలు ఉన్నాయి, అవి 6, 8 మరియు 10, 5 మరియు 10 మధ్య కలుపుకొని ఉంటాయి.

అల్గారిథం

  1. క్రమీకరించు శ్రేణి.
  2. బైనరీ శోధనను ఉపయోగించడం ద్వారా మూలకం y యొక్క శ్రేణి యొక్క ఎక్కువ సూచికను కనుగొనండి, ఎక్కువ సూచికను తిరిగి ఇవ్వండి.
  3. బైనరీ శోధనను ఉపయోగించి మూలకం x యొక్క శ్రేణి యొక్క చిన్న సూచికను కనుగొనండి, చిన్న సూచికను తిరిగి ఇవ్వండి.
  4. ఎక్కువ సూచిక మరియు చిన్న సూచిక మరియు ప్లస్ 1 మధ్య వ్యత్యాసాన్ని తిరిగి ఇవ్వండి.

వివరణ

మేము ఒక పూర్ణాంక శ్రేణిని మరియు x మరియు y అనే రెండు సంఖ్యలను ఇచ్చాము. ఇచ్చిన x మరియు y ల మధ్య ఉన్న ఇచ్చిన శ్రేణిలో ఉన్న మొత్తం సంఖ్యలను కనుగొనమని మేము కోరాము. సాధారణంగా, “x” కన్నా ఎక్కువ సంఖ్యల సంఖ్యను మనం కనుగొనాలి. మరియు “y” కన్నా చిన్న సంఖ్యల సంఖ్య. మేము శ్రేణిని క్రమబద్ధీకరిస్తాము. దీని వెనుక ఉన్న కారణం ఏమిటంటే, మేము బైనరీ శోధన పద్ధతిని ఉపయోగించబోతున్నాం. అది కూడా సవరించబడుతోంది.

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

మేము తక్కువ మరియు అధిక విలువ మధ్యలో పొందుతాము మరియు శ్రేణి [మధ్య] వద్ద ఉన్న మూలకం x కి సమానం కంటే ఎక్కువగా ఉందో లేదో తనిఖీ చేయండి. ఇది నిజమైతే, అధిక విలువను మధ్య -1 కు నవీకరించండి. తక్కువ నుండి మధ్య +1 విలువను నవీకరించండి. అదే y మూలకంతో వర్తించబడుతుంది. అయితే, ఆ సందర్భంలో, మేము ఎక్కువ సూచికను కనుగొంటాము మరియు శ్రేణిని తనిఖీ చేయడానికి బదులుగా [మధ్య] y కి సమానం. అప్పుడు శ్రేణి [మధ్య] y కి సమానం కంటే తక్కువగా ఉందో లేదో తనిఖీ చేస్తూ ఉండండి మరియు తక్కువ నుండి మధ్య + 1 విలువను మరియు అధిక విలువను మధ్య 1 కు నవీకరించండి.

రెండు సూచికలను ఎక్కువ మరియు చిన్నదిగా పొందండి మరియు వాటి వ్యత్యాసాన్ని తిరిగి ఇచ్చి దానికి 1 జోడించండి. ఇది మా అవసరమైన సమాధానం అవుతుంది. గుర్తుంచుకోండి, ఇచ్చిన పరిధిలోని విలువలతో శ్రేణి మూలకాల గణనల కోసం మేము ప్రశ్నలకు సమాధానం ఇవ్వాలనుకుంటున్నాము.

కోడ్

ఇచ్చిన పరిధిలో శ్రేణి మూలకాల సంఖ్యను కనుగొనడానికి C ++ కోడ్

#include<iostream>
#include<algorithm>

using namespace std;

int smallerElement(int arr[], int n, int x)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] >= x)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
int greaterElement(int arr[], int n, int y)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] <= y)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return high;
}
int countInRange(int arr[], int n, int x, int y)
{
    int count = 0;
    count = greaterElement(arr, n, y) - smallerElement(arr, n, x) + 1;
    return count;
}
int main()
{
    int arr[] = {2,4,6,8,1,10 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    int i = 2, j = 8;
    cout << countInRange(arr, n, i, j) << endl;

    i = 5, j = 10;
    cout << countInRange(arr, n, i, j) << endl;
    return 0;
}
4
3

ఇచ్చిన పరిధిలో శ్రేణి మూలకాల సంఖ్యను కనుగొనడానికి జావా ప్రోగ్రామ్

import java.io.*;
import java.util.Arrays;

class NumberOfElements
{
    private static int countInRange(int arr[], int n, int x, int y)
    {
        int count = 0;
        count = greaterElement(arr, n, y) -
                smallerElement(arr, n, x) + 1;
        return count;
    }
    
    private static int smallerElement(int arr[], int n, int x)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] >= x)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }
    
    private static int greaterElement(int arr[], int n, int y)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] <= y)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return high;
    }

    public static void main (String[] args)
    {
        int arr[] = {2,4,6,8,1,10 };
        int n = arr.length;

        Arrays.sort(arr);

        int x = 2, y = 8;
        System.out.println( countInRange(arr, n, x, y)); ;

        x = 5;
        y = 10;
        System.out.println( countInRange(arr, n, x, y));
    }
}
4
3

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

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

ప్రతి ప్రశ్నను అమలు చేయడానికి సమయం ఉంటుంది O (లాగ్ n) మరియు శ్రేణిని క్రమబద్ధీకరించడానికి ఒకసారి ఉంటుంది O (n లాగ్ n).

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

పై)  (ఇక్కడ  “N” శ్రేణిలోని మూలకాల సంఖ్య. శ్రేణిని క్రమబద్ధీకరించేటప్పుడు తీసుకున్న స్థలం కారణంగా మేము పరిగణించిన స్థలం. ఇన్‌పుట్‌ను నిల్వ చేయడానికి అవసరమైన స్థలం “ఇచ్చిన పరిధిలోని విలువలతో శ్రేణి మూలకాల గణనల కోసం ప్రశ్నలు” సమస్యలో పరిగణించబడదు.