a + b + c = d ကိုရှာဖို့ Array တွင်အကြီးဆုံး d ကိုရှာပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Accolite အမေဇုံ ဒေလီ ဝါသနာရှင်များ လေးကစ် FreeCharge
အခင်းအကျင်း hash

ပြProbleနာဖော်ပြချက်

မင်းမှာတစ်ခုရှိတယ်ဆိုပါစို့ အခင်းအကျင်း of ကိန်း။ input တန်ဖိုးများကိုအားလုံးကွဲပြားဒြပ်စင်ဖြစ်ကြသည်။ ပြlargestနာက“ အကြီးဆုံး d ကိုစစ်ခင်းခြင်းဖြင့်ရှာပါ၊ ထိုကဲ့သို့သော + b + c = d” ဟု သတ်မှတ်၍ အကြီးဆုံးဒြပ်စင် 'd' ကိုရှာရန်မေးသည်။ ဥပမာ + + b + c = d ။ ၎င်းမှာ element အားလုံးတစ်ခုနှင့်တစ်ခုကွဲပြားခြားနားသည်။

နမူနာ

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

ရှင်းလင်းချက်: ဂဏန်းသုံးလုံးက a, b နှင့် c သည် 1, 4 နှင့် 6 ဖြစ်ပြီးသူတို့ရဲ့ပေါင်းလဒ်သည် 11 ဖြစ်သည်။

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

ရှင်းလင်းချက်: ကိန်းဂဏန်းသုံးခုမရှိတဲ့အတွက်ကိန်းဂဏန်းတစ်ခုလုံးကိုစုစည်းထားတယ်။

algorithm

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.

ရှင်းလင်းချက်

စဉ်းစားပါ ကိန်း အခင်းအကျင်း ကွဲပြားကိန်း၏ပါဝင်သည်။ ကျွန်ုပ်တို့၏တာ ၀ န်မှာနံပါတ် ၃ ခုရှိသည့်နည်းကိုရှာဖွေရန်ဖြစ်သည်။ ငါတို့သုံးမယ် တားဆီးခြင်း။ Hashing တစ် ဦး အကျိုးရှိစွာဖြေရှင်းချက်ပေးပါသည်။ Array ကိုဖြတ်ပြီးတစ်ချိန်တည်းတွင် array element နှစ်ခုကိုယူပြီး၎င်းအတွဲများ၏ပေါင်းလဒ်ကိုသက်ဆိုင်ရာအညွှန်းများနှင့်အတူမြေပုံဆွဲပါ။

ငါတို့က d ကိုရှာနေတဲ့အတွက်ဒီစုံတွဲကိုသိမ်းထားလိမ့်မယ်။ + b + c = d ။ အဲဒီအစား + b = d - c ကိုရှာပါမယ်။ ဒီတော့ပထမတော့ငါတို့ pair တစုံနဲ့သူတို့ရဲ့ညွှန်းကိန်းတွေကိုသိမ်းမယ်။ မြေပုံထဲတွင် d - c တည်ရှိကြောင်းကို 'd' ကိုစစ်ဆေးနိုင်ပါမည်။ ၎င်းကို array ကိုဖြတ်သန်းပြီး element နှစ်ခုကိုတစ်ပြိုင်တည်းကောက်ယူခြင်းဖြင့်ပြုလုပ်နိုင်သည်။ ဒြပ်စင်နှစ်ခုလုံး၏ခြားနားချက်ကိုလုပ်ပြီးမြေပုံတွင်ရှိလျှင်ထိုခြားနားချက်ကိုရှာဖွေပါ။ အကယ်၍ ဤအရာသည်မှန်ကန်ကြောင်းတွေ့ရှိပါက၊ လက်ရှိဒြပ်စင်နှစ်ခုသည်အညွှန်းတွင်ရှိသည့်ယခင်အတွဲများကဲ့သို့တူညီသောအညွှန်းတွင်မဖြစ်သင့်ကြောင်းစစ်ဆေးပါ။

တူညီသောအညွှန်းတွင်ထပ်တူထပ်မံမပါ ၀ င်ခြင်းရှိမရှိစစ်ဆေးရန်လိုအပ်သည်။ ထပ်တလဲနံပါတ်ကို a, b, c နှင့် d တွင်ထည့်သွင်းစဉ်းစားနိုင်သည်။ သို့သော်၎င်းတို့၏ညွှန်းကိန်းများအရ၊ စဉ်းစားမရ။ ဒါကြောင့်ဒီညွှန်းကိန်းတွေ plagiarism ကိုစစ်ဆေးရမယ်။ ယခုကျွန်ုပ်တို့အမြင့်ဆုံး arr [i] နှင့် arr [j] ကိုရှာဖွေပြီး၎င်းအကြားရှိအမြင့်ဆုံးကိုရှာဖွေ။ d သို့သိုလှောင်ရန်ထိုအမြင့်ဆုံးကိုစစ်ဆေးရန်လိုအပ်သည်။ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည်စတုတ္ထမြောက်နံပါတ် d ကိုရှာဖွေရန်လိုအပ်သောကြောင့်ဖြစ်သည်။ ကျွန်ုပ်တို့သည်ကိန်းဂဏန်းအများဆုံးအစုများကိုရှာရန်လိုအပ်သည်။

အကောင်အထည်ဖော်ရေး

C + + သည် + 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

+ b + c = d ကဲ့သို့သော array ထဲတွင်အကြီးဆုံး d ကိုရှာရန် Java ပရိုဂရမ်ဖြစ်သည်

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

ထိုကဲ့သို့သော + b + c ကို = that ကြောင်းထိုကဲ့သို့သော Array အတွက်အကြီးမားဆုံး d ရှာရန်ရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာခြင်း

အချိန်ရှုပ်ထွေး

အို (။2ဘယ်မှာ “ n” သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ ကျွန်ုပ်တို့သည်ဤရှုပ်ထွေးမှုကိုအောင်မြင်ခဲ့ပြီဖြစ်သောကြောင့် O (1) အတွင်းထည့်သွင်းရှာဖွေခြင်းနှင့်အခြားလုပ်ဆောင်မှုများကိုခွင့်ပြုသည့် HashMap ကိုအသုံးပြုခဲ့သည်။

အာကာသရှုပ်ထွေးမှု

အို (။2) ဘယ်မှာ “ n” သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ အဆိုပါ HashMap input ကို၏ကွဲပြားခြားနားသောဒြပ်စင်၏ pair တစုံ၏ထို့အပြင်စတိုးဆိုင်ကတည်းက။ ထို့ကြောင့်၎င်း algorithm တွင် quadratic space ရှုပ်ထွေးမှုရှိသည်။

အညွှန်း