فرق جي قطار | اي (1) ۾ رينج اپڊيٽ سوال.


تڪليف جي سطح سخت
بار بار پڇڻ ۾ آرڪسيميم ڪوڊشن سڌو Expedia گوگل Qualcomm
ڪيريو سوال جو مسئلو

توھان کي ھڪڙو ڏنو وڃي ٿو انٽرويو صف ۽ ٻه قسم جي سوالن ، هڪ حد ۾ ڏنل نمبر شامل ڪرڻ ۽ ٻيو مڪمل ڇپائي لاءِ. مسئلو “فرق آريه | او (1) ۾ رينج اپڊيٽ سوال ”اسان کي اي (1) ۾ رينج اپڊيٽ انجام ڏيڻ جي ضرورت آهي.

مثال

arr[] = {20, 30, 25, 50}

Update(0, 1, 10)

print()

update(0, 2, 20)

update(2, 3, 30)

print()
(30 40 25 50) (50 60 75 80)

وضاحت

10 کي 20 ۽ 30 ۾ شامل ڪيو ويندو ، تنھنڪري صف {30 ، 40 ، 25 ، 50} ٿي ويندي

پوءِ اسان س arrayي صف کي ڇپينداسين.

20 30 ، 40 ، ۽ 25 ۾ شامل ڪيا ويندا ، تنھنڪري صف {50 ، 60 ، 45 ، 50} ٿي ويندي

10 کي 45 ۽ 50 ۾ شامل ڪيو ويندو ، تنھنڪري صف {50 ، 60 ، 75 ، 80} ٿي ويندي

پوءِ وري اسين س arrayي صف کي ڇپائينداسين.

سوالن کي انجام ڏيڻ کانپوءِ قدر جا ٻه سيٽ ڇپجي ويندا.

فرق جي قطار | اي (1) ۾ رينج اپڊيٽ سوال.

 

الگٽريءَ لاءِ الگوريٿم

  1. ساڳئي صف جي ھڪڙي سر ٺاهيو
  2. پهريون انڊيڪس ترتيب ڏيو جيئن صف جو پهريون عنصر ڏنو ويو آهي ، ۽ آخري انڊيڪس 0. ۽ ٻين سڀني اشارن کي موجوده ۽ پوئين عنصر جي فرق سان ڀريل آهي.
  3. هر تازه ڪاري سوال لاءِ ، ٺاهيل صف جي ڏنل کاٻي انڊيڪس ۾ قدر ايڪس شامل ڪريو ۽ ٺاهيل صف جي سا theي انڊيڪس مان ايڪس کي گھٽايو.
  4. هر پرنٽ جي سوال لاءِ ، پهريون فارمولا A [i] = D [i] + A [i-1] استعمال ڪندي داخل ڪيو ٿا. پوءِ اقدار ڇاپيو.

وضاحت

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

هڪ بهتر حل هتي بحث ڪيو ويو آهي ، جيڪو اهو هڪ اضافي صف ٺاهڻ آهي جو فرق محفوظ ڪري. ان ڪري ان کي فرق جي قطار سڏيو وڃي ٿو. پهرين ، فرسٽ صف جي پهرين عنصر کي انٽري صف جو پهريون عنصر ڏيو. پوءِ فرق جي آخري عنصر کي 0 کي تفويض ڪيو XNUMX ان کان پوءِ ، اسان صف بندي ذريعي نڪري وڃڻ وارا آهيون ۽ اسٽارٽ ۾ موجوده انڊيڪس تي موجوده ويليو ۽ پوئين ويل جي فرق کي اسٽور ڪندا آهيون.

اسان قيمتون ھڪڙي رينج جي طور تي حاصل ڪنداسين ، جيڪڏھن اسان کي تازه ڪاري سوال ملي ويو. گڏو گڏ اسان کي به هڪ نمبر مهيا ڪيو ويو آهي. ان کان پوء اسان انهي نمبر کي شامل ڪرڻ وارا آهيون قطار جي کاٻي پاسي جي اشاري ۾ فرق صف ۾. ساڳي طرح قدر آر کي فرق آرين جي سا indexي انڊيڪس مان ڪٽايو. صف کي ڇپائڻ لاءِ اسان صف ذريعي لنگھائينداسين ۽ صفر انڊيڪس ويليو لاءِ اسان ڏنل ترتيب جي قيمت کي اپڊيٽ ڪنداسين جيئن اسان ٺاهي اسان ٺاهي ، ٻي صورت ۾ اسان ٺاهي ٺاهيل سر جو مقدار ۽ ڏنل صف جي پوئين قيمت ۽ خاص اشاري لاءِ قيمت پرنٽ ڪيو.

ڪوڊ

C ++ ۾ تعارف ارريج لاءِ

#include<iostream>

using namespace std;

void buildArray(int arr[], int dummyArray[], int n)
{
    dummyArray[0] = arr[0];
    dummyArray[n] = 0;
    for (int i = 1; i < n; i++)
        dummyArray[i] = arr[i] - arr[i - 1];
}

static void update(int dummyArray[], int l, int r, int x)
{
    dummyArray[l] += x;
    dummyArray[r + 1] -= x;
}

void printArray(int arr[], int dummyArray[], int n)
{
    for (int i = 0; i <n; i++)
    {

        if (i == 0)
            arr[i] = dummyArray[i];
        else
            arr[i] = dummyArray[i] + arr[i - 1];

        cout<<arr[i] << " ";
    }

    cout<<endl;
}

int main()
{
    int arr[] = {20,30,25,50};
    int n = sizeof(arr)/sizeof(arr[0]);

    int dummyArray[n + 1];
    buildArray(arr, dummyArray, n);

    update(dummyArray, 0, 1, 10);
    printArray(arr, dummyArray, n);
    update(dummyArray, 0, 2, 20);
    update(dummyArray, 2, 3, 30);

    printArray(arr, dummyArray,n);
    return 0;
}
30 40 25 50
50 60 75 80

جاوا ۾ انفرافيشن ارريج ۾ عمل

class differenceArray
{
    static void buildArray(int arr[], int dummyArray[])
    {

        int n = arr.length;

        dummyArray[0] = arr[0];
        dummyArray[n] = 0;
        for (int i = 1; i < n; i++)
            dummyArray[i] = arr[i] - arr[i - 1];
    }
    
    static void update(int dummyArray[], int left, int right, int x)
    {
        dummyArray[left] += x;
        dummyArray[right + 1] -= x;
    }
    
    static int printArray(int arr[], int dummyArray[])
    {
        for (int i = 0; i < arr.length; i++)
        {
            if (i == 0)
                arr[i] = dummyArray[i];
            else
                arr[i] = dummyArray[i] + arr[i - 1];

            System.out.print(arr[i] + " ");
        }

        System.out.println();

        return 0;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {20, 30, 25, 50};
        int n = arr.length;
        int dummyArray[] = new int[n + 1];

        buildArray(arr, dummyArray);

        update(dummyArray, 0, 1, 10);
        printArray(arr, dummyArray);
        update(dummyArray, 0, 2, 20);
        update(dummyArray, 2, 3, 30);

        printArray(arr, dummyArray);
    }
}
30 40 25 50
50 60 75 80

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

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

اي (ق) جتي "ق" ڇا هڪ تازه ڪاري سوال جي طور تي انجام ڏيڻ واري پرنٽ سوالن جو تعداد هوندو آهي اي (1) وقت.

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

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي. اسان کان جڏهن هڪ اضافي فرق جوڙيو آهي ، اسان وٽ لڪيري اسپيس پيچيدگي آهي.