Rayանգվածում գտեք ամենամեծ d- ն այնպես, որ a + b + c = d


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Ակոլիտ Amazon Առաքում Ֆանատիկա Ֆուրկիտներ Անվճար լիցքավորում
Դասավորություն Խանգարել

Խնդիրի հայտարարություն

Ենթադրենք, որ դուք ունեք դասավորություն of ամբողջական թվերը, Մուտքային արժեքները բոլորը հստակ տարրեր են: «Rayանգվածում գտիր ամենամեծ 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.

բացատրություն

Դիտարկենք ան ամբողջ թիվ դասավորություն կազմված հստակ ամբողջ թվերից: Մեր խնդիրն է պարզել համարը այնպես, որ գոյություն ունեն երեք թվեր, որոնք ամփոփում են այդ թվին: Մենք պատրաստվում ենք օգտագործել Հեշինգ, Հաշինգը արդյունավետ լուծում է տալիս: Անցեք զանգվածը և միանգամից վերցրեք երկու զանգվածի տարրեր և պահեք այդ զույգերի հանրագումարը `իրենց համապատասխան ցուցիչներով քարտեզագրելու համար:

Մենք կպահենք զույգը, քանի որ փնտրում ենք d, այնպես որ a + b + c = d: Սրա փոխարեն մենք կփնտրենք + b = d - c: Այսպիսով, սկզբում, երբ մենք պահում ենք զույգը և դրանց ցուցանիշները: Մենք կկարողանանք ստուգել «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

Java ծրագիրը զանգվածում գտնել ամենամեծ 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

Timeամանակի բարդություն

Վրա2որտեղ «Ն» զանգվածում տարրերի քանակն է: Մենք հասել ենք այս բարդությանը, քանի որ օգտագործել ենք HashMap- ը, որը թույլ է տալիս տեղադրման որոնում և այլ գործողություններ O (1) ժամանակում:

Տիեզերական բարդություն

Վրա2) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ HashMap- ը պահում է ներդրման զույգ տարբեր տարրերի լրացում: Այդ պատճառով ալգորիթմն ունի քառակուսային տարածության բարդություն:

Մանրամասն