તત્વો ઉમેરવા માટે જેથી શ્રેણીના બધા ઘટકો એરેમાં હાજર હોય


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ગ્રેઓરેંજ કુલીઝા સ્નેપડીલ સારાંશ તેરાદાતા ટાઇમ્સ ઇન્ટરનેટ
અરે હેશ હેશિંગ સોર્ટિંગ

સમસ્યા નિવેદન

"તત્વો ઉમેરવા માટે જેથી શ્રેણીના બધા ઘટકો એરેમાં હાજર હોય" કહે છે કે તમને પૂર્ણાંકોની એરે આપવામાં આવે છે. સમસ્યાનું નિવેદન એરેમાં ઉમેરવા માટેના તત્વોની ગણતરી શોધવા માટે પૂછે છે જેથી બધા ઘટકો ઓછામાં ઓછા એક વખત એરેમાં સમાવિષ્ટ [X, Y] ની શ્રેણીમાં આવે. અનુક્રમે એક્સ અને વાય એરેની ન્યૂનતમ અને મહત્તમ સંખ્યા છે.

ઉદાહરણ

arr[] = {4,5,7,9,11}
3

સમજૂતી: એક્સ અને વાય 4 અને 11 છે (અનુક્રમે લઘુત્તમ અને મહત્તમ સંખ્યા), આ સંખ્યાની મર્યાદામાં, ફક્ત 3, 6, 8 અને 10 ગુમ છે.

તત્વો ઉમેરવા માટે જેથી શ્રેણીના બધા ઘટકો એરેમાં હાજર હોય

arr[] = {2,4,6,7}
2

સમજૂતી: એક્સ અને વાય 2 અને 7 (અનુક્રમે લઘુત્તમ અને મહત્તમ સંખ્યા) છે, આ સંખ્યાની મર્યાદામાં, ફક્ત 2 ગુમ થયેલ છે 3 અને 5.

ઉમેરવા માટે તત્વો શોધવા માટે એલ્ગોરિધમ જેથી શ્રેણીના બધા ઘટકો એરેમાં હાજર હોય

1. Declare a Set.
2. Set output to 0, minValue to the maximum value of integer and maxValue to the minimum value of an integer.
3. Traverse the array and put all the values into the set and simultaneously find out the maximum and the minimum number of an array and store it to the maxValue and minValue respectively.
4. Traverse the array again, from minValue to maxValue.
5. Check if the map doesn’t contain any of the elements in traversal, then, increase the count of output.
6. Return output.

સમજૂતી

અમારી પાસે છે પૂર્ણાંક એરે. સમસ્યા એરેમાં ઉમેરવા માટેના તત્વોની સંખ્યા શોધવા માટે છે. જેથી બધા તત્વો એરેની મહત્તમ અને લઘુત્તમ સંખ્યાની શ્રેણીમાં રહે જેથી કોઈ પણ તત્વો ઓછામાં ઓછા એકવાર ન આવે.

સમૂહની ઘોષણા કરો, સેટમાં ફક્ત એક જ વાર અલગ તત્વો સ્ટોર કરવા માટેની મિલકત છે. આનો અર્થ એ કે તે સામાન્ય તત્વોને દૂર કરે છે અને ફક્ત વિશિષ્ટ તત્વો સંગ્રહિત કરે છે. તેથી અમે તે કેસ સંભાળી શકશે. હવે આપણે સમૂહમાં બધા એરે તત્વો દાખલ કરવા જઈ રહ્યા છીએ. સાથોસાથ આપણે મહત્તમ અને લઘુત્તમ તત્વ શોધીશું. જેથી મહત્તમ અને મિનિટ શોધવા માટે અમારે કોઈ વધારાનું આક્રમણ કરવું ન પડે. છેવટે, આપણે ફક્ત શ્રેણીમાં ગુમ થયેલ તત્વોની ગણતરી શોધવાની જરૂર છે. તેથી ફક્ત સંખ્યાઓ ગણવાની જરૂર છે. અને આપણે પોતાને સંખ્યાઓ સાથે વ્યવહાર કરવાની જરૂર નથી.

હવે, આપણે એરેને લઘુત્તમ મૂલ્યથી શરૂ કરીને એરેના મહત્તમ મૂલ્ય સુધી જઈશું. કારણ કે આ એકમાત્ર રેન્જ છે જે આપણને જોઈએ છે. અમે શ્રેણીમાંની દરેક સંખ્યાને પસંદ કરીશું અને તપાસ કરીશું કે જો સેટમાં તે શ્રેણીનું મૂલ્ય નથી. જો સમૂહમાં તે વર્તમાન શ્રેણી મૂલ્ય શામેલ નથી, તો પછી આપણે આઉટપુટની ગણતરીમાં વધારો કરીશું. અને જ્યારે પણ અમારી પાસે સેટમાં રેન્જનું મૂલ્ય હાજર નથી ત્યારે પણ આઉટપુટનું મૂલ્ય 1 દ્વારા વધારીશું. જાણે કે ઉલ્લેખિત કોડમાં લઘુત્તમ 4 અને મહત્તમ 11 છે અને તે 6,8 અને 10 ની વચ્ચે (4,11) શ્રેણીમાં ગુમ થયેલ છે, પણ આ તત્વો એરેમાં હાજર નથી તેથી તે તત્વોની સંખ્યા ગણાશે. અને અંતે, આપણે તે આઉટપુટ આપીશું.

કોડ

ઉમેરવા માટેનાં તત્વો શોધવા માટે સી ++ કોડ જેથી શ્રેણીના તમામ ઘટકો એરેમાં હાજર હોય

#include<iostream>
#include<unordered_set>

using namespace std;

int getCountMissingNumber(int arr[], int n)
{
    unordered_set<int> SET;
    int output = 0;
    int maxValue = INT_MIN;
    int minValue = INT_MAX;

    for (int i = 0; i < n; i++)
    {
        SET.insert(arr[i]);
        if (arr[i] < minValue)
            minValue = arr[i];
        if (arr[i] > maxValue)
            maxValue = arr[i];
    }
    for (int a = minValue; a <= maxValue; a++)
    {
        if (SET.find(a) == SET.end())
        {
            output++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {4,5,7,9,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getCountMissingNumber(arr, n);
    return 0;
}
3

તત્વો ઉમેરવા માટે જાવા કોડ જેથી શ્રેણીના બધા તત્વો એરેમાં હાજર હોય

import java.util.HashSet;

class NumberBwRange
{
    public static int getCountMissingNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<>();
        int output = 0;
        int maxValue = Integer.MIN_VALUE;
        int minValue = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
            if (arr[i] < minValue)
                minValue = arr[i];
            if (arr[i] > maxValue)
                maxValue = arr[i];
        }

        for (int i = minValue; i <= maxValue; i++)
            if (!SET.contains(i))
                output++;
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 4,5,7,9,11 };
        int n = arr.length;
        System.out.println(getCountMissingNumber(arr, n));
    }
}
3

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (મહત્તમ - મિનિટ +1) જ્યાં “મહત્તમ” અને “મિનિટ” છે મહત્તમ અને ન્યુનત્તમ એરેનું મૂલ્ય. કારણ કે અમે લઘુત્તમ તત્વથી મહત્તમ તત્વ તરફ પ્રયાણ કર્યું છે. તેથી જ સૌથી ખરાબ સ્થિતિમાં આ મૂલ્ય એન તત્વોથી વધી શકે છે. તેથી, કારણ કે મહત્તમ-મીન + 1 એ એન કરતા મોટું હોઈ શકે છે. સમય જટિલતા ઓ (મહત્તમ-મિનિટ + 1) છે જ્યાં મહત્તમ મહત્તમ તત્વ સૂચવે છે, અને મિનિમમ ન્યૂનતમ તત્વ સૂચવે છે.

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. કારણ કે આપણે ફક્ત N તત્વો સંગ્રહિત કરી રહ્યા છીએ, એલ્ગોરિધમમાં રેખીય અવકાશ જટિલતા છે.