array palindrome ٺاھڻ لاءِ گھٽ ۾ گھٽ انرنگ آپريشن کي ڳوليو


تڪليف جي سطح آسان
بار بار پڇڻ ۾ قبول ڪريو ايڊوب Amazon چار چار
ڪيريو لالچ Math

مسئلي جو بيان

توھان کي ھڪڙو ڏنو وڃي ٿو صف انٽيگرن جو مسئلو بيان ڪيو ويو آهي ته آرڊر پلنڊروم ٺاهڻ لاءِ گهٽ ۾ گهٽ انٽيگريشن آپريشن گهٽ ۾ گهٽ ملن ، يعني ميئر آپريشنز جو گهٽ ۾ گهٽ انگ ڳوليو وڃي ته اهو آرينڊ تي پئنڊروم ٺاهيو وڃي. ضم ٿيڻ واري آپريشن جو مطلب اهو آهي ته اسان ڪل سان ملايو ويو عنصرن جو مجموعو ٺاهي سگهون ٿا.

مثال

arr[] = {1, 4, 6, 6, 5}
1

وضاحت: اسان 1 ۽ 4 کي پاڻ جو مجموعو بڻائي سگھون ٿا ، تنھنڪري اھو 5 ٿي وڃي ٿو ۽ اسان جو قطار {5 ، 6 ، 6 ، 5} ٿي وڃي ٿو ، جيڪو ھڪ پيلنڊروم آھي.

arr[] = {2,1,2,4,3}
2

وضاحت: اسان 1 ۽ 2 کي انهن جي سٿ سان ضم ڪري سگهون ٿا ، تنهن ڪري اهو 3 ٿئي ٿو ۽ 2 ۽ 4 پڻ ضم ٿي سگهن ٿا ، تنهن ڪري اسان جو جوڙ {3 ، 6 ، 3} ٿي وڃي ٿو

 

الورگرافم کي مرڻ آپريشن جي گھٽ ۾ گھٽ تعداد ڳولڻ لاءِ صف بندوبست ڪرڻ لاءِ

1. Set the value of output to 0.
2. Traverse the array from i = 0 and j = n – 1, to i < n( length of an array).
  1. If arr[i] is equal to arr[j]
    1. Do i++ and j--.
  2. If arr[i] > arr[j]
    1. Do j—
    2. Update and restore the value of arr[j] = arr[j] + arr[j+1].
    3. Increase the output’s value by 1.
  3. If arr[i] < arr[j],
    1. Increase the value of i.
    2. Update arr[i] = arr[i] + arr[i-1].
    3. Increase the output’s value by 1.
3. Return output.

 

وضاحت

اسان انٽيگرز جي هڪ قطار ڏني آهي. اسان کي چيو ويو آهي ته گهٽ ۾ گهٽ نمبر ڳولڻ جي لاءِ ملائڻ آپريشن جيڪي صف ٿي سگھن ٿا ان کي ھلائڻ لاءِ پيچندرو صف. هتي ضم ٿيڻ جو مطلب آهي ٻه ڀرپاسي وارو قدر شامل ڪرڻ ۽ انهن کي انهن جي مجموعي سان تبديل ڪرڻ. هتي اسان ڳولهڻ لاءِ گھڻا آپريشن ڪيا پيا وڃن.

اسان کي بائیں کان ۽ پڻ دڙي ٺاهڻ واري صف کي لنگهڻ وارا آهيون ، هر پوائنٽ انڊيڪس جي پوزيشن کي ظاهر ڪندي. اسان ٻنهي طرفن کي چونڊيو ڇاڪاڻ ته اسان کي پڙتال ڪرڻي آهي ته اهو پيلنڊيروم آهي يا نه. ۽ ٻنهي طرفن کان پئنڊروم ۾ انهن جي انڊيڪس جي مطابق عناصر ساڳيا هوندا آهن جيئن پئنڊرروم ۾. تنهن ڪري اسان مخالف طرفن جي قيمت چيڪ ڪنداسين ۽ انهن جي انڊيڪس تي هلائينداسين. ان کان پوءِ اسان ميگريشن آپريشن ڪندا آهيون ۽ تيستائين آپريشن جاري رکون ٿا جيسين ميگريشن آپريشن ڪرڻ جي ڳڻپ نه ڪئي وڃي

اسان چڪاس ڪنداسين ته کاٻي کان کاٻي ۽ سا elementي عنصر برابر آهن. پوءِ صرف مرڪز کي ون يونٽ طرف اشارو ڪيو. انهي لاءِ چڪاس ڪريو ته کاٻي پوائنٽر انڊيڪس عنصر دائيٽ پوائنٽر انڊيڪس عنصر کان وڏو آهي ، پوءِ سا poي پوائنٽر ويليو جي قيمت کي گھٽائي ڇڏيو ۽ ويجهي عناصر جي مجموعي سان arr [j] کي اپ ڊيٽ ڪريو ۽ ٻاھر ويليو جي قيمت کي وڌائيندي مطلب اسان جي تعداد. آپريشن.

اسان اهو چيڪ ڪنداسين ته کاٻي پوائنٽر انڊيڪس عنصر دائي پوائنٽر انڊيڪس عنصر کان نن isو آهي ، پوءِ کاٻي پوائنٽر جي قيمت کي وڌائين ۽ ڀرپاسي عنصرن جي مجموعي سان arr [i] کي اپڊيٽ ڪريو ۽ محصول جي قيمت ۾ وڌايل معنيٰ اسان جي. آپريشن جو تعداد ۽ آخر ۾ ، اسان پيداوار جي قدر واپس آڻينداسين.

array palindrome ٺاھڻ لاءِ گھٽ ۾ گھٽ انرنگ آپريشن کي ڳوليو

آرين پلنڊروم ٺاهڻ لاءِ گهٽ ۾ گهٽ آپريشن جي نظام ڳولڻ لاءِ ڪوڊ

سي ++ ڪوڊ

#include<iostream>

using namespace std;

int getMinimumOperation(int arr[], int n)
{
    int output = 0;

    for (int i=0,j=n-1; i<=j;)
    {
        if (arr[i] == arr[j])
        {
            i++;
            j--;
        }
        else if (arr[i] > arr[j])
        {
            j--;
            arr[j] += arr[j+1] ;
            output++;
        }
        else
        {
            i++;
            arr[i] += arr[i-1];
            output++;
        }
    }
    return output;
}
int main()
{
    int arr[] = { 1, 4, 6, 6, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Minimum operations to be done: "<< getMinimumOperation(arr, n);
    return 0;
}
Minimum operations to be done: 1

 

جاوا ڪوڊ

class ArrayPalindromeMerging
{
    public static int getMinimumOperation(int[] arr, int n)
    {
        int output = 0;
        for (int i=0,j=n-1; i<=j;)
        {
            if (arr[i] == arr[j])
            {
                i++;
                j--;
            }
            else if (arr[i] > arr[j])
            {
                j--;
                arr[j] += arr[j+1] ;
                output++;
            }
            else
            {
                i++;
                arr[i] += arr[i-1];
                output++;
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 6, 6, 5} ;
        System.out.println("Minimum operations to be done : "+ getMinimumOperation(arr, arr.length));
    }
}
Minimum operations to be done : 1

 

پيچيدگي تجزيي

وقت جي پيچيدگي

اسان سادي طور تي هڪ ڀيرو تياري ڪري رهيا آهيون ، انهي ڪري اهو ڳڻپيوڪر وقت جي پيچيدگين لاءِ آهي. اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.

خلائي پيچيدگي

اسان صرف هڪ واحد صف کي استعمال ڪري رهيا آهيون ، ج ن کي ان پٽ کي اسٽور ڪرڻ جي لاءِ ، اهڙي طرح هي الگورتھم ميري آپريشن کي گھڻائي جي لاءِ ڳولڻ جي لاءِ صف ترتيب ڏئي رهيو آهي. اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.