Пронађите минималну удаљеност између два броја


Ниво тешкоће Лако
Често питани у ЦоупонДуниа Цоурсера Делхивери Моонфрог Лабс ПаиПал Паитм Снапцхат
Ред

Изјава о проблему

Дали сте низ и два броја названа к и и. Проблем „Пронађи најмању удаљеност између два броја“ тражи да се утврди најмања могућа удаљеност између њих. Дати низ може имати заједничке елементе. Можете претпоставити да су и к и и различити.

Пример

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.

Објашњење

Дали смо поредак целих бројева и два целобројна броја звана к и и. Морамо да сазнамо минималну удаљеност између два дата броја, к и и. Да бисмо сазнали минималну удаљеност проверићемо два бројевна пара. Број који смо добили, проверићемо само за њих током преласка. Тражићемо један од два броја који се подудара са тренутним елементом низа. Ако се утврди да је тачно, проверићемо да ли се ради о понављајућем елементу или о истом елементу. Ако се утврди да су сви услови тачни, ми ћемо само ажурирати излазну вредност.

Било који од тренутних елемената низа једнак је к или и, а други услов индекса и истих елемената постао је нетачан. Тада ћемо само ажурирати заставицу и сместити тренутни индекс елемената у заставицу. Размотримо пример и погледајмо то:

Пример

Арр [] = {1, 3, 2, 5, 8, 2, 5, 1}, к = 2, и = 8

Излаз = максимална вредност целог броја, заставица = - 1

Дали смо два броја к = 2 и и = 8

  • и = 0, проверићемо да ли је арр [и] једнако 2 или је арр [и] једнако 8, али услов не задовољава.

Услов задовољава када је и = 2.

  • и = 2, арр [и] је једнако 2.

Проверићемо да ли има заставе и она је нетачна јер је застава и даље -1. Дакле, неће ући ако, само ћемо ажурирати заставицу као флаг = 2.

  • Следећи избор, када је и = 4, арр [и] = 8, застава није једнака -1, а такође арр [и] није једнака арр [застава]. Проверавамо ово стање како не бисмо поново пронашли исти број и утврдили његову удаљеност.

Дакле, сада ћемо ажурирати излаз као = 4 - 2 = 2. И такође ажурирати заставицу = 4

  • Опет на и = 5, арр [и] = 2, наћи ћемо услов тачно, а такође заставица није једнака -1 и арр [и] није једнака арр [застава], па ћемо извод поново ажурирати као минимум између мин (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

Анализа сложености

Сложеност времена

Појединачно прелажење чини алгоритам да ради у линеарној временској сложености. Он) где „Н“ је број елемената у низу.

Сложеност простора

НА) сложеност простора, јер користимо низ за чување улаза. Али алгоритам за проналажење минималне удаљености захтева О (1) додатни простор.