Add parts of 1 Array in all Subarrays of dimension M of different Array

By
Sohaib
-
0
9
Adv1


Adv2

Given two arrays arr1[] and arr2[] of dimension N and M (M < N) add all parts of arr2[] in all doable subarrays of arr1[] of dimension M precisely as soon as. The duty is to return the ultimate array arr1[] after performing the above operations.

Examples: 

Enter: arr1[] = {1, 1, 1, 1, 1}, arr2[] = {1, 1, 1}
Output:  2 3 4 3 2
Clarification: There are precisely 3 subarrays of dimension M in arr1[] 
including corresponding parts of arr2[] in first subarray from ingredient 1 to 3. arr1[] turns into {2, 2, 2, 1, 1}
including corresponding parts of arr2[] in second subarray from ingredient 2 to 4. arr1[] turns into {2, 3, 3, 2, 1}
including corresponding parts of arr2[] within the third subarray from parts 3 to 5. arr1[] turns into {2, 3, 4, 3, 2}

Enter: arr1[] = {1, 2, 3, 4, 5}, arr2[] = {10}
Output: 11 12 13 14 15

Naive Method: The issue could be solved utilizing linear iteration primarily based on the next concept:

Preserve including all parts of arr2[] in all doable subarrays of dimension M of arr1[]. There shall be precisely N – M + 1 subarrays.

Observe the steps talked about beneath to implement the thought:

  • Iterate from i = 0 to N-M+1:
    • Iterate from j = 0 to M:
      • Add arr2[j] with arr[i+j.
  • Return the final state of arr1[] because the required reply.

Beneath is the implementation of the above strategy.

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

void addArr2ToArr1(int arr1[], int arr2[], int N, int M)

{

    

    

    

    for (int i = 0; i < N - M + 1; i++) {

  

        

        

        

        for (int j = 0; j < M; j++) {

            arr1[i + j] = arr1[i + j] + arr2[j];

        }

    }

  

    

    for (int i = 0; i < N; i++) {

        cout << arr1[i] << " ";

    }

    cout << endl;

}

  

int important()

{

    int arr1[] = { 1, 1, 1, 1, 1 }, arr2[] = { 1, 1, 1 };

    int N = sizeof(arr1) / sizeof(arr1[0]);

    int M = sizeof(arr2) / sizeof(arr2[0]);

  

    

    addArr2ToArr1(arr1, arr2, N, M);

  

    int arr3[] = { 10, 11, 12, 13, 14 }, arr4[] = { 10 };

    int N2 = sizeof(arr3) / sizeof(arr3[0]);

    int M2 = sizeof(arr4) / sizeof(arr4[0]);

  

    

    addArr2ToArr1(arr3, arr4, N2, M2);

  

    int arr5[] = { 12, 11, 10, 9 },

        arr6[] = { 1, 2, 3, 4, 5 };

    int N3 = sizeof(arr5) / sizeof(arr5[0]);

    int M3 = sizeof(arr6) / sizeof(arr6[0]);

  

    

    addArr2ToArr1(arr5, arr6, N3, M3);

  

    return 0;

}
Output

2 3 4 3 2 
20 21 22 23 24 
12 11 10 9

Time Complexity: O(N * M)
Auxiliary Area: O(1)

Environment friendly Method: The above strategy could be optimized primarily based on the next concept:

This may be noticed each ingredient i of arr1[] may have some vary of parts from arr2[] that will get added.
For instance.
in case of arr1[] = {0, 0, 0, 0, 0}, arr2[] = {1, 2, 3}
ingredient 1 may have 1 in its sum. Vary of parts that bought added from arr2[] is [0, 0].
ingredient 2 may have 1 and a pair of in its sum. Vary of parts that bought added from arr2[] is [0, 1].
ingredient 3 may have 1, 2, and three in its sum. Vary of parts that bought added from arr2[] is [0, 2].
ingredient 4 may have 2 and three in its sum. Vary of parts that bought added of arr2[] is  [1, 2].
ingredient 5 may have 3 in its sum. Vary of parts that bought added of arr2[] is  [2, 2].

Commentary: each ingredient ‘i’ may have sum of parts of arr2[] from max(0, M – N + i) to min(i, M-1).
Sum from max(1, M – N + i) to min(i, M-1) could be calculated utilizing prefix sum in fixed time. 

Observe the steps beneath to resolve the issue:

  • Initializing prefix[] array which shall be used to retailer the sum of all ranges of arr2[].
  • Initializing L = max(1, M – N + i) and R = min(i, M).
  • Traverse  from 1 to N, Including prefix[R] – prefix[L  – 1] in arr[i – 1] . 
  • print the ultimate array

Beneath is the implementation of the above strategy.

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

void addArr2ToArr1(int arr1[], int arr2[], int N, int M)

{

    

    

    int prefix[M + 1] = { 0 };

  

    

    for (int i = 1; i <= M; i++) {

        prefix[i] = prefix[i - 1] + arr2[i - 1];

    }

  

    for (int i = 1; i <= N; i++) {

  

        

        

        int r = min(i, M), l = max(1, M - N + i);

  

        

        

        

        

        

        arr1[i - 1]

            = arr1[i - 1] + prefix[r] - prefix[l - 1];

    }

  

    for (int i = 0; i < N; i++) {

        cout << arr1[i] << " ";

    }

}

  

int important()

{

    int arr1[] = { 1, 1, 1, 1, 1 }, arr2[] = { 1, 1, 1 };

    int N = sizeof(arr1) / sizeof(arr1[0]);

    int M = sizeof(arr2) / sizeof(arr2[0]);

  

    

    addArr2ToArr1(arr1, arr2, N, M);

  

    return 0;

}

Time Complexity: O(N)
Auxiliary Area: O(M)

Associated Articles:

Adv3