கொடுக்கப்பட்ட வரம்பில் சம உறுப்புகளைக் கொண்ட குறியீடுகளின் எண்ணிக்கை


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது கிரே ஆரஞ்சு உண்மையில் வேலை இடுகைகள் Snapdeal யாகூ
அணி வினவல் சிக்கல்

உங்களுக்கு ஒரு வழங்கப்படுகிறது முழு வரிசை, q வினவல்கள் மற்றும் இடது மற்றும் வலது என ஒரு வரம்பு. “கொடுக்கப்பட்ட வரம்பில் சமமான கூறுகளைக் கொண்ட குறியீடுகளின் எண்ணிக்கை” <= i <வலதுபுறம் விட்டுச் செல்லும் வழியில் முழு எண்களின் எண்ணிக்கையைக் கண்டுபிடிக்க கூறுகிறதுi = அj + 1.

உதாரணமாக

arr[] = {2, 2, 3, 3, 3, 4, 4, 4, 4}
Query = 2
Left = 2, right = 6
Left = 4, right = 8
3
3

விளக்கம்

வினவல் 1 க்கு, இடது = 2, வலது = 6

arr[2]=arr[3], arr[3]=arr[4], arr[5]=arr[6]

எண்ணிக்கை 3 ஆகும்.

வினவல் 2 க்கு, இடது = 4, வலது = 8

arr[5]=arr[6], arr[6]=arr[7], arr[7]=arr[8]

எண்ணிக்கை 3 ஆகும்.

கொடுக்கப்பட்ட வரம்பில் சம உறுப்புகளைக் கொண்ட குறியீடுகளின் எண்ணிக்கை

 

அல்காரிதம்

  1. ஒரு வரிசையை உருவாக்கவும்.
  2. வரிசை வழியாக பயணிக்கவும்.
  3. தற்போதைய வரிசை உறுப்பு அடுத்த உறுப்புக்கு சமமாக இருந்தால், உருவாக்கப்பட்ட வரிசையின் உறுப்பு 1 க்கு சமம் என்று குறிக்கவும்.
  4. குறியீட்டு எண் 0 க்கு சமமாக இல்லாவிட்டால், வரிசை டம்மியின் தற்போதைய வரிசை உறுப்பு மற்றும் அடுத்த வரிசை உறுப்பு ஆகியவற்றை வரிசை டம்மியில் சேமிக்கவும் [i].
  5. வினவலைத் தீர்க்கவும், இடது நிலை 0 க்கு சமமாக இருந்தால், அரேடம்மி [வலது -1] ஐத் திருப்பி விடுங்கள், இல்லையெனில் வரிசை டம்மி [வலது -1] மற்றும் வரிசை டம்மி [இடது -1] ஆகியவற்றின் வேறுபாட்டைத் தரவும்.

விளக்கம்

எங்களுக்கு ஒரு வழங்கப்படுகிறது முழு வரிசை, மற்றும் இடது பக்கமாகவும் வலது பக்கமாகவும் ஒரு வரம்பு. அருகிலுள்ள கூறுகள் ஒருவருக்கொருவர் சமமாக இருக்கும் வகையில் குறியீடுகளின் எண்ணிக்கையைக் கண்டுபிடிக்கும்படி கேட்கப்படுகிறோம். இரண்டு வெவ்வேறு குறியீடுகளுடன், இரண்டு சமமான அருகிலுள்ள உறுப்புகளைக் கண்டறிந்தால், 1 மற்றும் பலவற்றை எண்ணுங்கள். பின்னர் அதிகபட்ச அளவிலான வரிசையை உருவாக்குகிறோம். கொடுக்கப்பட்ட நிபந்தனையை பூர்த்தி செய்யும் குறியீட்டைக் கணக்கிடும் ஒரு செயல்பாட்டை நாங்கள் உருவாக்கியுள்ளோம். நிபந்தனை என்னவென்றால், அருகிலுள்ள இரண்டு கூறுகள் ஒருவருக்கொருவர் சமமாக இருக்கும்.

தொடக்கத்தில் இருந்து வரிசையின் நீளத்தை விட குறைவான ஒரு வழியாக நாம் பயணிப்போம். வரிசையின் தற்போதைய உறுப்பு வரிசையின் அடுத்த உறுப்புக்கு சமமாக இருக்கிறதா என்று சரிபார்க்கிறோம். நிபந்தனை உண்மை எனக் கண்டறியப்பட்டால். அந்த மதிப்பை தற்போதைய குறியீட்டில் 1 முதல் 1 எனக் குறிக்கிறோம். இந்த 1 ஐக் குறிப்போம், ஏனென்றால் அருகிலுள்ள எந்த உறுப்புகளும் சமமாக இருக்கிறதா என்பதை அறிந்து கொள்வோம். ஒவ்வொரு ஜோடியும் எண்ணிக்கை 2 ஆகவும், முந்தைய ஜோடிக்கு பொதுவான ஒரு உறுப்புடன் அடுத்த ஜோடி 1 ஆகவும் கணக்கிடப்படும். N ஜோடிகள் சமமாக இருந்தால் n-0 இன் எண்ணிக்கை இருக்கும். குறியீட்டு மதிப்பு XNUMX இல்லையென்றால், அது முதல் உறுப்பு இல்லையென்றால் பயணிக்கும் போது. வரிசை டம்மி மின்னோட்டத்தின் உறுப்பு மற்றும் முந்தைய உறுப்பு ஆகியவற்றின் தொகையை தற்போதைய வரிசை குறியீட்டில் வரிசை டம்மியின் சேமிக்கவும்.

வரம்பின் இடது குறியீடு 0 க்கு சமமாக இருந்தால் கொடுக்கப்பட்ட ஒவ்வொரு வினவலுக்கும், பின்னர் வரிசை டம்மியை [வலது - 1] திரும்பவும். அது 0 இல்லையென்றால், அரேடம்மி [வலது - 1] மற்றும் அரேடம்மி [இடது - 1] ஆகியவற்றுக்கு இடையிலான வித்தியாசத்தைத் திருப்பி விடுங்கள்.

குறியீடு

கொடுக்கப்பட்ட வரம்பில் சம உறுப்புகளைக் கொண்ட குறியீடுகளின் எண்ணிக்கை எண்ணுவதற்கு சி ++ குறியீடு

#include <iostream>

using namespace std;

int arrayDummy[100];

void getNumbers(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] == a[i + que
            arrayDummy[i] = 1;

        if (i != 0)
            arrayDummy[i] += arrayDummy[i - 1];
    }
}

int solveQuery(int l, int r)
{
    if (l == 0)
        return arrayDummy[r - 1];
    else
        return arrayDummy[r - 1] - arrayDummy[l - 1];
}

int main()
{
    int arr[] = { 2,2,3,3,3,4,4,4,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    getNumbers(arr, n);

    int left, right;

    left = 2;
    right = 6;

    cout << solveQuery(left, right) << endl;
    left = 4;
    right = 8;
    cout << solveQuery(left, right) << endl;
    return 0;
}
3
3

கணக்கிட ஜாவா குறியீடு கொடுக்கப்பட்ட வரம்பில் சம உறுப்புகளைக் கொண்ட குறியீடுகளின் எண்ணிக்கை

class IndexElementsEqual
{
    static int arrayDummy[] = new int[1000];

    public static void getNumbers(int arr[], int n)
    {
        for (int i = 0; i < n-1; i++)
        {
            if (arr[i] == arr[i + 1])
                arrayDummy[i] = 1;

            if (i != 0)
                arrayDummy[i] += arrayDummy[i - 1];
        }
    }
    public static int solveQuery(int left, int right)
    {
        if (left == 0)
            return arrayDummy[right - 1];
        else
            return arrayDummy[right - 1] - arrayDummy[left - 1];
    }
    public static void main(String args[])
    {
        int arr[] = {2,2,3,3,3,4,4,4,4};
        int n = arr.length;

        getNumbers(arr, n);

        int left, right;

        left = 2;
        right = 6;

        System.out.println(solveQuery(left, right));
        left = 4;
        right = 8;
        System.out.println(solveQuery(left, right));
    }
}
3
3

சிக்கலான பகுப்பாய்வு

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

 ஓ (1) ஒவ்வொரு வினவலுக்கும் மற்றும் ஓ (n) முன் கணிப்பீட்டிற்கு.

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

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. வரிசை டம்மியை உருவாக்க இந்த இடம் தேவை.