Најдете го најголемиот d во низата така што a + b + c = d


Ниво на тешкотија Медиум
Често прашувано во Аколит Амазон Деливерија Фанатици Фуркити Бесплатно полнење
Низа Хаш

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

Да претпоставиме дека имате низа of цели броеви. Влезните вредности се сите различни елементи. Проблемот „Најди го најголемиот d во низата, така што a + b + c = d“ бара да го открие најголемиот елемент „d“ во множеството, така што a + b + c = d, каде што сите елементи се различни едни од други.

пример

arr[] = {1, 4, 6, 8, 11 }
11

објаснување: Трите броја a, b и c се 1, 4 и 6 и нивниот збир е 11.

arr[] = {2,4,6,10,15 }
No such solution exists.

објаснување: Бидејќи нема три броја, тоа се сумира до број.

Алгоритам

1. Declare a Map.
2. While traversing through the array.
    1. Add and insert the sum of two elements in a map with their indexes in a Map.
3. Set the number to the minimum value of an integer, which we have to find out.
4. Search for the third number in a map by checking the difference of two numbers is present in a map.
5. If true then check if their indexes should not be the same.
6. Check for the maximum of d and the maximum of arr[i] and arr[j] and store it to d.
7. Return d.

Објаснување

Размислете за еден број низа се состои од изразити цели броеви. Нашата задача е да го откриеме бројот на таков начин, постојат три броја кои се сумираат на тој број. Е користиме Хашинг. Хаширањето дава ефикасно решение. Поминете низ низата и земете два елементи од низата истовремено и зачувајте го збирот на тие парови за мапирање со нивните соодветни индекси.

Willе го зачуваме парот затоа што бараме d, така што a + b + c = d. Наместо ова, ќе бараме + b = d - c. Отпрвин, кога ќе ги зачуваме парот и нивните индекси. Beе можеме да провериме за елементот "d", така што d - c постои на картата. Ова може да се направи со пресекување на низата, а потоа подигање на два елементи одеднаш. Направете разлика и од елементите и побарајте ја таа разлика доколку постои на картата. Ако ова се покажа како точно, проверете ги тековните два елементи не треба да бидат на истиот индекс како и претходните парови на индексот.

Ова е потребно за да се провери дали некој од елементите не треба да се повторува на истиот индекс, повторениот број може да се разгледа во a, b, c и d, но нивните индекси, што треба да се каже, самиот број на истиот индекс треба да не се смета. Значи, мора да провериме дали има индекси на плагијат. Сега, треба да ги откриеме максимумот на arr [i] и arr [j] и да го провериме тој максимум до d за да го откриеме максимумот помеѓу нив и да го зачуваме до d. Бидејќи, треба да го откриеме четвртиот број d, затоа треба да го најдеме максимумот на елементите на низата, бидејќи d е секогаш поголем меѓу a, b, c и d.

Имплементација

Програма C ++ за наоѓање на најголемиот d во низата, така што a + b + c = d

#include<iostream>
#include<unordered_map>

using namespace std;

int getSumThreeNumber(int arr[], int n)
{
    unordered_map<int, pair<int, int> > MAP;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            MAP[arr[i] + arr[j]] = { i, j };
        }
    }
    int d_number = INT_MIN;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int third = abs(arr[i] - arr[j]);

            if (MAP.find(third) != MAP.end())
            {
                pair<int, int> obj = MAP[third];
                if (obj.first != i && obj.first != j && obj.second != i && obj.second != j)
                    d_number = max(d_number, max(arr[i], arr[j]));
            }
        }
    }
    return d_number;
}
int main()
{
    int arr[] = { 1,4,6,8,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int res = getSumThreeNumber(arr, n);
    if (res == INT_MIN)
        cout << "No such solution exists";
    else
        cout << res;
    return 0;
}
11

Јава програма за наоѓање на најголемиот d во низата, така што a + b + c = d

import java.util.HashMap;

class CheckIndex
{
    int i, j;

    CheckIndex(int i, int j)
    {
        this.i = i;
        this.j = j;
    }
    int checkI()
    {
        return i;
    }

    int checkJ()
    {
        return j;
    }
}

class sumOfThreeElementToD
{

    public static int getSumThreeNumber(int[] arr, int n)
    {
        HashMap<Integer, CheckIndex> map = new HashMap<>();

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                map.put(arr[i] + arr[j], new CheckIndex(i, j));
            }
        }

        int d_number = Integer.MIN_VALUE;

        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int third = Math.abs(arr[i] - arr[j]);

                if (map.containsKey(third))
                {
                    CheckIndex ci = map.get(third);
                    if (ci.checkI() != i && ci.checkI() != j && ci.checkJ() != i && ci.checkJ() != j)
                    {
                        d_number = Math.max(d_number, Math.max(arr[i], arr[j]));
                    }
                }
            }
        }
        return d_number;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 6, 8, 11 };
        int n = arr.length;
        int output = getSumThreeNumber(arr, n);
        if (output == Integer.MIN_VALUE)
            System.out.println("No such solution exists");
        else
            System.out.println(output);
    }
}
11

Анализа на сложеност за наоѓање на најголемиот d во низата, така што a + b + c = d

Временска комплексност

На2каде „Н“ е бројот на елементи во низата. Ја постигнавме оваа сложеност затоа што користевме HashMap што овозможува пребарување на вметнување и други операции во време О (1).

Комплексноста на просторот

На2) каде „Н“ е бројот на елементи во низата. Бидејќи HashMap складира додаток на пар различни елементи на влезот. Поради ова, алгоритмот има квадратна просторна сложеност.

Суд