બે સંખ્યા વચ્ચે ન્યુનત્તમ અંતર શોધો  


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે કુપનદુનિયા Coursera દિલ્હીવારી મૂનફ્રોગ લેબ્સ પેપાલ પેટીએમ Snapchat
અરે

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

તમે એરે અને બે નંબરો આપ્યા છે જેને x અને y કહેવામાં આવે છે. સમસ્યા "બે સંખ્યા વચ્ચે ન્યુનત્તમ અંતર શોધો" તેમની વચ્ચેનું ઓછામાં ઓછું સંભવિત અંતર શોધવા માટે પૂછે છે. આપેલ એરેમાં સામાન્ય તત્વો હોઈ શકે છે. તમે ધારી શકો છો કે x અને y બંને અલગ છે.

ઉદાહરણ  

arr[] = {1, 3, 2, 5, 8, 2, 5, 1}

x = 2

y=8
1

સમજૂતી: 2 ના સૂચકાંકો 2 અને 5 છે અને 8 ની અનુક્રમણિકા 4 છે, તેથી અમે અનુક્રમણિકા લઈએ છીએ જે આપેલ બે નંબરો વચ્ચે લઘુતમ અંતરની ગણતરી કરે છે.

arr[] = {1, 3, 2, 5, 8, 2, 5, 1}

x = 3

y=5
2

સમજૂતી: 3 નું અનુક્રમણિકા 1 છે અને 5 નું અનુક્રમણિકા 3 છે. તેથી તે બંને વચ્ચે લઘુત્તમ અંતર 3-1 = 2 છે.

arr[] = {2, 4, 6, 8, 2, 5, 0, 56}

x = 6

y=5
3

સમજૂતી: 6 નું અનુક્રમણિકા 2 છે અને 5 નું અનુક્રમણિકા 5 છે, તેથી તે બંને વચ્ચે લઘુત્તમ અંતર 5-2 = 3 છે.

બે સંખ્યા વચ્ચે ન્યુનત્તમ અંતર શોધવા માટે એલ્ગોરિધમ  

1. Set flag to -1 and output to the Maximum value of an Integer.
2. Traverse the array from i = 0 to i < n.
    1. Check if the array element is either equal to x or equal to y.
    2. Check if flag is not equal to i and arr[i] is not equal to arr[flag].
        1. If the condition is true, then find out the minimum between the output and i - flag.
3. Return output.

સમજૂતી

અમે એક આપ્યો છે એરે પૂર્ણાંકો અને બે પૂર્ણાંક નંબરો અને x અને y કહેવાય છે. આપણે આપેલ બે નંબરો, x અને y વચ્ચેનું ન્યુનત્તમ અંતર શોધવાનું છે. ન્યૂનતમ અંતર શોધવા માટે, અમે બે સંખ્યાની જોડી ચકાસીશું. અમને જે નંબર આપવામાં આવે છે, અમે તે ફક્ત ટ્રversવર્સલ દરમિયાન જ તપાસીશું. આપણે એ બે નંબરોમાંથી કોઈ એક શોધીશું, એરે વર્તમાન તત્વ સાથે મેળ ખાતી છે. જો તે સાચું હોવાનું જણાયું છે, તો અમે તપાસ કરીશું કે તે પુનરાવર્તિત તત્વ નથી અથવા તે જ તત્વ નથી. જો બધી શરતો સાચી જણાય છે, તો અમે ફક્ત આઉટપુટ મૂલ્યને અપડેટ કરીશું.

આ પણ જુઓ
આપેલ શ્રેણીમાં સમાન અથવા વિચિત્ર સંખ્યાની સંભાવના પર પ્રશ્નો

હાલનું કોઈપણ એરે એલિમેન્ટ x અથવા y ની બરાબર છે, અને અનુક્રમણિકાઓ અને તે જ તત્વોની બીજી શરત ખોટી થઈ ગઈ છે. પછી અમે ફક્ત ધ્વજને અપડેટ કરીશું અને વર્તમાન તત્વ અનુક્રમણિકાને ફ્લેગમાં સંગ્રહિત કરીશું. ચાલો આપણે એક ઉદાહરણ ધ્યાનમાં લઈએ અને તેના પર એક નજર કરીએ:

ઉદાહરણ

અરે [] = {1, 3, 2, 5, 8, 2, 5, 1}, x = 2, y = 8

આઉટપુટ = પૂર્ણાંકનું મહત્તમ મૂલ્ય, ધ્વજ = - 1

અમે બે નંબરો આપ્યા છે x = 2 અને y = 8

  • i = 0, આપણે તપાસ કરીશું કે એરર [i] 2 અથવા arr બરાબર છે કે નહીં [i] 8 ની બરાબર છે, પરંતુ સ્થિતિ સંતોષતી નથી.

જ્યારે સ્થિતિ = i = 2 થાય ત્યારે સંતોષ થાય છે.

  • i = 2, એરર [i] બરાબર 2 છે.

અમે ધ્વજની તપાસ કરીશું અને તે ખોટું છે કારણ કે ધ્વજ હજી -1 છે. તેથી તે દાખલ થશે નહીં, જો આપણે ફક્ત ફ્લેગ = 2 તરીકે ધ્વજને અપડેટ કરીશું.

  • આગલું ચૂંટો, જ્યારે હું = 4, એઆર [i] = 8, ધ્વજ -1 ની બરાબર નથી અને એરે પણ [i] એઆરઆર [ફ્લેગ] ની બરાબર નથી. અમે આ સ્થિતિની તપાસ કરી રહ્યા છીએ જેથી અમને ફરીથી તે જ નંબર ન મળે અને તેનું અંતર ન મળે.

તો હવે આપણે આઉટપુટ = 4 - 2 = 2. તરીકે અપડેટ કરીશું અને ફ્લેગ = 4 પણ અપડેટ કરીશું

  • ફરીથી i = 5, એરે [i] = 2 પર, આપણે શરત સાચી શોધીશું, અને ધ્વજ -1 ની બરાબર નહીં અને એરે [i] એઆર [ફ્લેગ] ની બરાબર નહીં, તેથી આપણે ફરીથી આઉટપુટ અપડેટ કરીશું. ન્યૂનતમ મિનિટ (4, 5-4) અને 1 આઉટપુટમાં અપડેટ થશે.

તેથી હવે આપણી પાસે એરે એલિમેન્ટ એરે [1] = 4 અને એરે [8] = 5 ની વચ્ચે ન્યૂનતમ અંતર 2 છે.

આ પણ જુઓ
મહત્તમ કદના સબરા્રેનો સરવાળો કે

આઉટપુટ = 1.

બે સંખ્યા વચ્ચે ન્યુનત્તમ અંતર શોધોપિન

કોડ  

બે સંખ્યા વચ્ચે ન્યુનત્તમ અંતર શોધવા માટે સી ++ કોડ

#include<bits/stdc++.h>

using namespace std;

int getMinimumDistance(int arr[], int n, int x, int y)
{
    int flag=-1;
    int output=INT_MAX;

    for(int i = 0 ; i < n ; i++)
    {
        if(arr[i] ==x || arr[i] == y)
        {
            if(flag != -1 && arr[i] != arr[flag])
            {
                output = min(output,i-flag);
            }

            flag=i;
        }
    }
    if(output==INT_MAX)
        return -1;

    return output;
}

int main()
{
    int arr[] = {1, 3, 2, 5, 8, 2, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 2;
    int y = 8;

    cout << "Minimum possible distance between " << x <<" and " << y << " : "<<getMinimumDistance(arr, n, x, y);
    return 0;
}
Minimum possible distance between 2 and 8 : 1

બે સંખ્યા વચ્ચે ન્યુનત્તમ અંતર શોધવા માટે જાવા કોડ

class MinimumDistanceBwNumbers
{
    public static int getMinimumDistance(int arr[], int n, int x, int y)
    {
        int flag=-1;
        int output=Integer.MAX_VALUE;

        for(int i = 0 ; i < n ; i++)
        {
            if(arr[i] ==x || arr[i] == y)
            {
                if(flag != -1 && arr[i] != arr[flag])
                {
                    output = Math.min(output,i-flag);
                }

                flag=i;
            }
        }
        if(output==Integer.MAX_VALUE)
            return -1;

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 3, 2, 5, 8, 2, 5, 1};
        int n = arr.length;
        int x = 2;
        int y = 8;

        System.out.println("Minimum possible distance between " + x + " and " + y + ": " + getMinimumDistance(arr, n, x, y));
    }
}
Minimum possible distance between 2 and 8: 1

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

સમય જટિલતા

સિંગલ ટ્રversવર્સલ રેખીય સમય જટિલતામાં અલ્ગોરિધમનો ચલાવવા માટે બનાવે છે. ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

અવકાશ જટિલતા

ઓ (એન) જગ્યા સંકુલ કારણ કે આપણે ઇનપુટ સંગ્રહવા માટે એરેનો ઉપયોગ કરીએ છીએ. પરંતુ ન્યૂનતમ અંતર શોધવા માટે અલ્ગોરિધમ માટે O (1) વધારાની જગ્યાની જરૂર છે.