ਫਰਕ ਐਰੇ | ਓ (1) ਵਿੱਚ ਸੀਮਾ ਅਪਡੇਟ ਪੁੱਛਗਿੱਛ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਆਰਸੀਸੀਅਮ ਕੋਡਨੇਸ਼ਨ ਦਿਸ਼ਾ ਇਕਸਪੀਡੀਆ ਗੂਗਲ 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} ਬਣ ਜਾਏਗੀ

ਫਿਰ ਅਸੀਂ ਪੂਰੀ ਐਰੇ ਨੂੰ ਪ੍ਰਿੰਟ ਕਰਾਂਗੇ.

20 ਨੂੰ 30, 40 ਅਤੇ 25 ਵਿਚ ਸ਼ਾਮਲ ਕੀਤਾ ਜਾਵੇਗਾ, ਇਸ ਲਈ ਐਰੇ {50, 60, 45, 50} ਬਣ ਜਾਏਗੀ

10 ਨੂੰ 45 ਅਤੇ 50 ਵਿਚ ਜੋੜਿਆ ਜਾਵੇਗਾ, ਇਸ ਲਈ ਐਰੇ {50, 60, 75, 80} ਬਣ ਜਾਏਗੀ

ਫਿਰ ਦੁਬਾਰਾ ਅਸੀਂ ਸਾਰੀ ਐਰੇ ਪ੍ਰਿੰਟ ਕਰਾਂਗੇ.

ਵੈਲਯੂਜ ਦੇ ਦੋ ਸੈਟ ਸੈਸ਼ਨ ਪ੍ਰਸ਼ਨ ਕਰਨ ਤੋਂ ਬਾਅਦ ਛਾਪੇ ਜਾਣਗੇ.

ਫਰਕ ਐਰੇ | ਓ (1) ਵਿੱਚ ਸੀਮਾ ਅਪਡੇਟ ਪੁੱਛਗਿੱਛ

 

ਫਰਕ ਐਰੇ ਲਈ ਐਲਗੋਰਿਦਮ

  1. ਦਿੱਤੇ ਗਏ ਐਰੇ ਦੇ ਬਰਾਬਰ ਅਕਾਰ ਦੀ ਇੱਕ ਐਰੇ ਬਣਾਓ.
  2. ਦਿੱਤੇ ਗਏ ਐਰੇ ਦੇ ਪਹਿਲੇ ਐਲੀਮੈਂਟ ਦੇ ਰੂਪ ਵਿੱਚ ਪਹਿਲੇ ਇੰਡੈਕਸ ਨੂੰ ਅਰੰਭ ਕਰੋ, ਅਤੇ ਆਖਰੀ ਸੂਚਕਾਂਕ 0 ਨਾਲ. ਅਤੇ ਹੋਰ ਸਾਰੇ ਸੂਚਕਾਂਕ ਮੌਜੂਦਾ ਅਤੇ ਪਿਛਲੇ ਤੱਤ ਦੇ ਅੰਤਰ ਨਾਲ ਭਰੇ ਹੋਏ ਹਨ.
  3. ਹਰੇਕ ਅਪਡੇਟ ਪੁੱਛਗਿੱਛ ਲਈ, ਬਣਾਏ ਗਏ ਐਰੇ ਦੇ ਦਿੱਤੇ ਖੱਬੇ ਇੰਡੈਕਸ ਵਿੱਚ ਵੈਲਯੂ ਐਕਸ ਸ਼ਾਮਲ ਕਰੋ ਅਤੇ ਐਰੇ ਨੂੰ ਐਰੇ ਨੂੰ ਬਣਾਏ ਐਰੇ ਦੇ ਸੱਜੇ ਇੰਡੈਕਸ ਤੋਂ ਘਟਾਓ.
  4. ਹਰੇਕ ਪ੍ਰਿੰਟ ਪੁੱਛਗਿੱਛ ਲਈ, ਪਹਿਲਾਂ ਅਸੀਂ ਫਾਰਮੈਟ A [i] = D [i] + A [i-1] ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ ਇਨਪੁਟ ਐਰੇ ਨੂੰ ਭਰਦੇ ਹਾਂ. ਫਿਰ ਮੁੱਲਾਂ ਨੂੰ ਪ੍ਰਿੰਟ ਕਰੋ.

ਕਥਾ

ਇੱਕ ਐਰੇ ਅਤੇ ਇੱਕ ਨੰਬਰ ਅਤੇ ਦੋ ਕਿਸਮਾਂ ਦੇ ਪ੍ਰਸ਼ਨ ਦਿੱਤੇ ਗਏ. ਇਸ ਲਈ ਸਾਨੂੰ ਦੋ ਕਿਸਮਾਂ ਦੇ ਪ੍ਰਸ਼ਨ ਪੁੱਛਣੇ ਹਨ. ਸਾਡੇ ਕੋਲ ਇੱਕ ਨੰਬਰ X ਦੇ ਨਾਲ ਇੱਕ ਸੀਮਾ ਦੀ ਨੁਮਾਇੰਦਗੀ ਕਰਨ ਲਈ ਦੋ ਨੰਬਰ ਹੋਣਗੇ. Theੰਗਾਂ ਵਿਚੋਂ ਇਕ ਹੋ ਸਕਦਾ ਹੈ ਇਕ ਭੋਲੀ ਪਹੁੰਚ ਦੀ ਵਰਤੋਂ ਕਰੋ. ਉਸ ਲਈ, ਹਰ ਵਾਰ ਦਿੱਤੀ ਗਈ ਐਰੇ ਨੂੰ ਪਾਰ ਕਰੋ ਜਦੋਂ ਵੀ ਸਾਨੂੰ ਵੈਲਯੂਜ਼ ਨੂੰ ਅਪਡੇਟ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੁੰਦੀ ਹੈ.

ਇੱਥੇ ਇੱਕ ਬਿਹਤਰ ਹੱਲ ਦੀ ਚਰਚਾ ਕੀਤੀ ਗਈ ਹੈ, ਜੋ ਕਿ ਇੱਕ ਵਾਧੂ ਐਰੇ ਬਣਾਉਣਾ ਹੈ ਜੋ ਅੰਤਰ ਨੂੰ ਸੰਭਾਲਦਾ ਹੈ. ਇਸ ਲਈ ਇਸ ਨੂੰ ਫਰਕ ਐਰੇ ਕਿਹਾ ਜਾ ਰਿਹਾ ਹੈ. ਪਹਿਲਾਂ, ਇੰਪੁੱਟ ਐਰੇ ਦੇ ਪਹਿਲੇ ਐਲੀਮੈਂਟ ਦੇ ਤੌਰ ਤੇ ਫਰਕ ਐਰੇ ਦੇ ਪਹਿਲੇ ਐਲੀਮੈਂਟ ਨੂੰ ਅਰੰਭ ਕਰੋ. ਫਿਰ ਫਰਕ ਐਰੇ ਦਾ ਆਖਰੀ ਤੱਤ 0 ਨੂੰ ਨਿਰਧਾਰਤ ਕਰੋ. ਉਸਤੋਂ ਬਾਅਦ, ਅਸੀਂ ਐਰੇ ਵਿੱਚੋਂ ਲੰਘਣ ਜਾ ਰਹੇ ਹਾਂ ਅਤੇ ਮੌਜੂਦਾ ਮੁੱਲ ਅਤੇ ਪਿਛਲੇ ਮੁੱਲ ਦੇ ਅੰਤਰ ਨੂੰ ਮੌਜੂਦਾ ਇੰਡੈਕਸ ਵਿੱਚ ਫਰਕ ਐਰੇ ਵਿੱਚ ਸਟੋਰ ਕਰਾਂਗੇ.

ਜੇ ਸਾਨੂੰ ਇੱਕ ਅਪਡੇਟ ਪੁੱਛਗਿੱਛ ਮਿਲਦੀ ਹੈ, ਤਾਂ ਸਾਨੂੰ ਰੇਂਜ ਦੇ ਰੂਪ ਵਿੱਚ ਵੈਲਯੂ ਮਿਲ ਜਾਣਗੇ. ਨਾਲ ਹੀ ਸਾਨੂੰ ਇੱਕ ਨੰਬਰ ਵੀ ਪ੍ਰਦਾਨ ਕੀਤਾ ਜਾਂਦਾ ਹੈ. ਫੇਰ ਅਸੀਂ ਉਹ ਨੰਬਰ ਜੋੜਨ ਜਾ ਰਹੇ ਹਾਂ ਫਰਕ ਐਰੇ ਵਿੱਚ ਸੀਮਾ ਦੇ ਖੱਬੇ ਸੂਚਕਾਂਕ ਤੇ. ਇਸੇ ਤਰ੍ਹਾਂ ਫਰਕ ਐਰੇ ਦੇ ਸੱਜੇ ਇੰਡੈਕਸ ਤੋਂ ਵੈਲਯੂ X ਨੂੰ ਘਟਾਓ. ਐਰੇ ਨੂੰ ਪ੍ਰਿੰਟ ਕਰਨ ਲਈ ਅਸੀਂ ਐਰੇ ਨੂੰ ਪਾਰ ਕਰਾਂਗੇ ਅਤੇ ਜ਼ੀਰੋ ਇੰਡੈਕਸ ਵੈਲਯੂ ਲਈ ਅਸੀਂ ਦਿੱਤੇ ਐਰੇ ਦੀ ਵੈਲਯੂ ਨੂੰ ਜੋ ਅਸੀ ਬਣਾਇਆ ਹੈ, ਨੂੰ ਅਪਡੇਟ ਕਰਾਂਗੇ, ਨਹੀਂ ਤਾਂ ਸਾਨੂੰ ਬਣਾਈ ਗਈ ਐਰੇ ਦਾ ਜੋੜ ਅਤੇ ਦਿੱਤੇ ਹੋਏ ਐਰੇ ਦਾ ਪਿਛਲੇ ਮੁੱਲ ਮਿਲੇਗਾ ਅਤੇ ਖਾਸ ਇੰਡੈਕਸ ਲਈ ਉਹ ਮੁੱਲ ਪ੍ਰਿੰਟ ਕਰੋ.

ਕੋਡ

ਫਰਕ ਐਰੇ ਲਈ 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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਕਿ)) ਜਿੱਥੇ ਕਿ "Q" ਇੱਕ ਅਪਡੇਟ ਪੁੱਛਗਿੱਛ ਵਿੱਚ ਲਿਆਂਦੇ ਜਾਣ ਅਨੁਸਾਰ ਪ੍ਰਿੰਟ ਪ੍ਰਸ਼ਨਾਂ ਦੀ ਗਿਣਤੀ ਹੈ ਓ (1) ਸਮਾਂ

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਕਿਉਕਿ ਅਸੀਂ ਇੱਕ ਵਾਧੂ ਅੰਤਰ ਅੰਤਰ ਨੂੰ ਬਣਾਇਆ ਹੈ, ਸਾਡੇ ਕੋਲ ਲੀਨੀਅਰ ਸਪੇਸ ਗੁੰਝਲਤਾ ਹੈ.