News Leaflets
0 6

Given two arrays arr1[] and arr2[] of size N and M (M < N) add all elements of arr2[] in all possible subarrays of arr1[] of size M exactly once. The task is to return the final array arr1[] after performing the above operations.

Examples:

Input: arr1[] = {1, 1, 1, 1, 1}, arr2[] = {1, 1, 1}
Output:  2 3 4 3 2
Explanation: There are exactly 3 subarrays of size M in arr1[]
adding corresponding elements of arr2[] in first subarray from element 1 to 3. arr1[] becomes {2, 2, 2, 1, 1}
adding corresponding elements of arr2[] in second subarray from element 2 to 4. arr1[] becomes {2, 3, 3, 2, 1}
adding corresponding elements of arr2[] in the third subarray from elements 3 to 5. arr1[] becomes {2, 3, 4, 3, 2}

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

Naive Approach: The problem can be solved using linear iteration based on the following idea:

Keep adding all elements of arr2[] in all possible subarrays of size M of arr1[]. There will be exactly N – M + 1 subarrays.

Follow the steps mentioned below to implement the idea:

• Iterate from i = 0 to N-M+1:
• Iterate from j = 0 to M:
• Return the final state of arr1[] as the required answer.

Below is the implementation of the above approach.

## C++

 ` `  `#include ` `using` `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` `main()` `{` `    ``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 Space: O(1)

Efficient Approach: The above approach can be optimized based on the following idea:

This can be observed every element i of arr1[] will have some range of elements from arr2[] that gets added.
For example.
in case of arr1[] = {0, 0, 0, 0, 0}, arr2[] = {1, 2, 3}
element 1 will have 1 in its sum. Range of elements that got added from arr2[] is [0, 0].
element 2 will have 1 and 2 in its sum. Range of elements that got added from arr2[] is [0, 1].
element 3 will have 1, 2, and 3 in its sum. Range of elements that got added from arr2[] is [0, 2].
element 4 will have 2 and 3 in its sum. Range of elements that got added of arr2[] is  [1, 2].
element 5 will have 3 in its sum. Range of elements that got added of arr2[] is  [2, 2].

Observation: every element ‘i’ will have sum of elements 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) can be calculated using prefix sum in constant time.

Follow the steps below to solve the problem:

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

Below is the implementation of the above approach.

## C++

 ` `  `#include ` `using` `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` `main()` `{` `    ``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 Space: O(M)

Related Articles: