दुई संख्या बीच न्यूनतम दूरी खोज्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ कुपनडुनिया Coursera दिल्लीवरी मूनफ्रग ल्याबहरू PayPal पेटम Snapchat
एरे

समस्या वक्तव्य

तपाईले एउटा एर्रे र दुई नम्बरहरु x र y दिईएको छ। समस्या "दुई संख्या बीच न्यूनतम दूरी फेला पार्नुहोस्" उनीहरू बीच न्यूनतम संभव दूरी पत्ता लगाउन सोध्छ। दिइएको एर्रेमा सामान्य तत्वहरू हुन सक्छन्। तपाई मान्न सक्नुहुन्छ कि दुबै x र y फरक छन्।

उदाहरणका

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

x = 2

y=8
1

स्पष्टीकरण: २ को सूचकहरू २ र are हुन् र of को सूचकांक is हो, त्यसैले हामी सूचकांक लिन्छौं जुन दुई दिइएको संख्याको बीचमा न्यूनतम दूरीको गणना गर्दछ।

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

x = 3

y=5
2

स्पष्टीकरण: of को सूचकांक १ हो र of को सूचकांक is हो। त्यसैले ती दुबै बीच न्यूनतम दूरी -3-११ = २ हो।

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

x = 6

y=5
3

स्पष्टीकरण: of को सूचकांक २ हो र of को सूचकांक is हो, त्यसैले तिनीहरू दुबै बीच न्यूनतम दूरी -6-२ = is हो।

दुई संख्या बीच न्यूनतम दूरी खोज्न एल्गोरिथ्म

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.

स्पष्टीकरण

हामीले एउटा दिएका छौं array पूर्णा .्क र दुई पूर्णांक संख्याको x र y भनिन्छ। हामीले दुई दिइएको संख्या, x र y बीचमा न्यूनतम दूरी पत्ता लगाउनु पर्छ। न्यूनतम दूरी पत्ता लगाउन हामी दुई संख्या जोडीहरू जाँच गर्नेछौं। नम्बर जुन हामीलाई दिइएको छ, हामी उनीहरूको लागि मात्र ट्रभर्सल जाँच गर्ने छौं। हामी दुई मध्ये एउटा नम्बर खोज्दैछौं, एरे वर्तमान एलिमेन्टसँग मेल खान्छ। यदि यो सहि पाइएको छ भने, हामी जाँच गर्नेछौं कि यो दोहोरिने तत्त्व वा उही तत्व होईन। यदि सबै सर्तहरू सही पाइएको छ भने, हामी मात्र आउटपुट मूल्य अपडेट गर्नेछौं।

कुनै पनि हालको एरे एलिमेन्ट या त x वा y सँग बराबर छ, र अनुक्रमणिकाको अर्को सर्त र उही तत्वहरू झूटा भएको छ। त्यसोभए हामी भर्खरै फ्ल्याग अपडेट गर्नेछौं र झण्डामा वर्तमान तत्व सूचकांक भण्डार गर्नेछौं। हामी एउटा उदाहरण विचार गरौं र यसमा एक नजर राखौं:

उदाहरणका

एर [] = {१,,, २,,,,, २,,, १}, x = २, y =

आउटपुट = एक पूर्णांकको अधिकतम मान, फ्ल्याग = - १

हामीले दुई अंकहरू x = २ र y = given दिएका छौं

  • i = ०, हामी जाँच गर्नेछौं यदि अरर [i] २ बराबर छ वा एर [i] 0 बराबर छ, तर सर्तले सन्तोष गरेन।

कन्डिसन सन्तोष हुन्छ जब i = २।

  • i = २, एर [i] २ बराबर छ।

हामी झण्डाका लागि जाँच गर्नेछौं र यो गलत छ किनकि झण्डा अझै -१ हो। त्यसो भए यो प्रवेश गर्दैन यदि हामी झण्डालाई झण्डा २ को रूपमा अपडेट गर्नेछौं।

  • अर्को छनौट, जब i =,, एर [i] =,, झण्डा -१ बराबर हुँदैन र एर पनि [i] अरर [झण्डा] बराबर हुँदैन। हामी यो सर्त जाँच गर्दैछौं ताकि हामी फेरी उस्तै नम्बर फेला पार्ने छैन र यसको दूरी प्राप्त गर्‍यौं।

अब हामी आउटपुट = 4 - २ = २ को रूपमा अपडेट गर्नेछौं र साथै झण्डा = update पनि अपडेट गर्नेछौं

  • फेरि i = at, एर [i] = २ मा, हामी कन्डिसन सहि फेला पार्नेछौं, र साथै झण्डा पनि -१ बराबर छैन र एर [i] अरर [झण्डा] सँग बराबर छैन, त्यसैले हामी आउटपुटलाई यस रूपमा फेरि अपडेट गर्नेछौं। न्यूनतम (,, -5--2) र १ बीचमा आउटपुटमा अपडेट हुनेछ।

त्यसैले अब हामीसँग एर्रे एलिमेन्ट एर []] = and र एर []] = २ बीचको न्यूनतम दूरी १ छ।

आउटपुट = १।

दुई संख्या बीच न्यूनतम दूरी खोज्नुहोस्

कोड

C ++ कोड दुई संख्या बीच न्यूनतम दूरी खोज्न

#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

जटिलता विश्लेषण

समय जटिलता

एकल traversal लाई एल्गोरिथ्म लाईन समय जटिलतामा चलाउँछ। ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो।

ठाउँ जटिलता

O (N) स्पेस जटिलता किनकि हामी इनपुट भण्डारण गर्न एर्रे प्रयोग गर्छौं। तर न्यूनतम दूरी खोज्नको लागि एल्गोरिथ्मको लागि ओ (१) थप ठाउँ चाहिन्छ।