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:
- Add arr2[j] with arr[i+j.
- 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++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the final state of arr1[]void addArr2ToArr1(int arr1[], int arr2[], int N, int M){ // Iterating through all possible subarrays // of size M in arr1[] there will be // exactly N - M + 1 subarrays for (int i = 0; i < N - M + 1; i++) { // Iterating through M elements of arr2[] // and adding in arr1[]'s 'i'th subarray's // 'i + j' th element for (int j = 0; j < M; j++) { arr1[i + j] = arr1[i + j] + arr2[j]; } } // Printing finally array for (int i = 0; i < N; i++) { cout << arr1[i] << " "; } cout << endl;}// Driver programint 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]); // Function call for testcase 1 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]); // Function call for testcase 2 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]); // Function call for testcase 3 addArr2ToArr1(arr5, arr6, N3, M3); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to find the final state of arr1[] static void addArr2ToArr1(int[] arr1, int[] arr2, int N, int M) { // Iterating through all possible subarrays // of size M in arr1[] there will be // exactly N - M + 1 subarrays for (int i = 0; i < N - M + 1; i++) { // Iterating through M elements of arr2[] // and adding in arr1[]'s 'i'th subarray's // 'i + j' th element for (int j = 0; j < M; j++) { arr1[i + j] = arr1[i + j] + arr2[j]; } } // Printing finally array for (int i = 0; i < N; i++) { System.out.print(arr1[i] + " "); } System.out.println(); } public static void main(String[] args) { int[] arr1 = { 1, 1, 1, 1, 1 }; int[] arr2 = { 1, 1, 1 }; int N = arr1.length; int M = arr2.length; // Function call for testcase 1 addArr2ToArr1(arr1, arr2, N, M); int[] arr3 = { 10, 11, 12, 13, 14 }; int[] arr4 = { 10 }; int N2 = arr3.length; int M2 = arr4.length; // Function call for testcase 2 addArr2ToArr1(arr3, arr4, N2, M2); int[] arr5 = { 12, 11, 10, 9 }; int[] arr6 = { 1, 2, 3, 4, 5 }; int N3 = arr5.length; int M3 = arr6.length; // Function call for testcase 3 addArr2ToArr1(arr5, arr6, N3, M3); }}// This code is contributed by lokesh. |
Python3
# python code# Function to find the final state of arr1[]def addArr2ToArr1(arr1, arr2, N, M): # Iterating through all possible subarrays # of size M in arr1[] there will be # exactly N - M + 1 subarrays for i in range(0, N - M + 1): # Iterating through M elements of arr2[] # and adding in arr1[]'s 'i'th subarray's # 'i + j' th element for j in range(0, M): arr1[i + j] = arr1[i + j] + arr2[j] # Printing finally array for i in range(0, N): print(arr1[i], end=" ") print()# Driver programarr1 = [1, 1, 1, 1, 1]arr2 = [1, 1, 1]N = len(arr1)M = len(arr2)# Function call for testcase 1addArr2ToArr1(arr1, arr2, N, M)arr3 = [10, 11, 12, 13, 14]arr4 = [10]N2 = len(arr3)M2 = len(arr4)# Function call for testcase 2addArr2ToArr1(arr3, arr4, N2, M2)arr5 = [12, 11, 10, 9]arr6 = [1, 2, 3, 4, 5]N3 = len(arr5)M3 = len(arr6)# Function call for testcase 3addArr2ToArr1(arr5, arr6, N3, M3)# This code is contributed by ksam24000 |
C#
// C# code to implement the approachusing System;class GFG { // Function to find the final state of arr1[] static void addArr2ToArr1(int[] arr1, int[] arr2, int N, int M) { // Iterating through all possible subarrays // of size M in arr1[] there will be // exactly N - M + 1 subarrays for (int i = 0; i < N - M + 1; i++) { // Iterating through M elements of arr2[] // and adding in arr1[]'s 'i'th subarray's // 'i + j' th element for (int j = 0; j < M; j++) { arr1[i + j] = arr1[i + j] + arr2[j]; } } // Printing finally array for (int i = 0; i < N; i++) { Console.Write(arr1[i] + " "); } Console.WriteLine(); } // Driver program public static void Main() { int[] arr1 = { 1, 1, 1, 1, 1 }; int[] arr2 = { 1, 1, 1 }; int N = arr1.Length; int M = arr2.Length; // Function call for testcase 1 addArr2ToArr1(arr1, arr2, N, M); int[] arr3 = { 10, 11, 12, 13, 14 }; int[] arr4 = { 10 }; int N2 = arr3.Length; int M2 = arr4.Length; // Function call for testcase 2 addArr2ToArr1(arr3, arr4, N2, M2); int[] arr5 = { 12, 11, 10, 9 }; int[] arr6 = { 1, 2, 3, 4, 5 }; int N3 = arr5.Length; int M3 = arr6.Length; // Function call for testcase 3 addArr2ToArr1(arr5, arr6, N3, M3); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
// Function to find the final state of arr1[]function addArr2ToArr1(arr1, arr2, N, M) { // Iterating through all possible subarrays // of size M in arr1[] there will be // exactly N - M + 1 subarrays for (let i = 0; i < N - M + 1; i++) { // Iterating through M elements of arr2[] // and adding in arr1[]'s 'i'th subarray's // 'i + j' th element for (let j = 0; j < M; j++) { arr1[i + j] = arr1[i + j] + arr2[j]; } } // Printing finally array for (let i = 0; i < N; i++) { console.log(arr1[i]); } console.log();}// Driver programlet arr1 = [1, 1, 1, 1, 1];let arr2 = [1, 1, 1];let N = arr1.length;let M = arr2.length;// Function call for testcase 1addArr2ToArr1(arr1, arr2, N, M);let arr3 = [10, 11, 12, 13, 14];let arr4 = [10];let N2 = arr3.length;let M2 = arr4.length;// Function call for testcase 2addArr2ToArr1(arr3, arr4, N2, M2);let arr5 = [12, 11, 10, 9];let arr6 = [1, 2, 3, 4, 5];let N3 = arr5.length;let M3 = arr6.length;// Function call for testcase 3addArr2ToArr1(arr5, arr6, N3, M3); |
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++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to add corresponding// elements of arr2[] in all possible// subarrays of size M of arr1[]void addArr2ToArr1(int arr1[], int arr2[], int N, int M){ // Prefix sum array will be used // to store sum of all ranges of arr2[] int prefix[M + 1] = { 0 }; // Taking prefix sum for (int i = 1; i <= M; i++) { prefix[i] = prefix[i - 1] + arr2[i - 1]; } for (int i = 1; i <= N; i++) { // Add element i of arr1[] with range of // elements of arr2[] from l to r int r = min(i, M), l = max(1, M - N + i); // Every element 'i' of arr1[] will // have sum of elements of arr2[] from // max(1, M - N + i) to min(i, M-1) which // can be calculate using prefix // sum in constant time arr1[i - 1] = arr1[i - 1] + prefix[r] - prefix[l - 1]; } for (int i = 0; i < N; i++) { cout << arr1[i] << " "; }}// Driver programint 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]); // Function call addArr2ToArr1(arr1, arr2, N, M); return 0;} |
Java
// Java code to implement the approachimport java.util.*;public class GFG { // Function to add corresponding // elements of arr2[] in all possible // subarrays of size M of arr1[] static void addArr2ToArr1(int arr1[], int arr2[], int N, int M) { // Prefix sum array will be used // to store sum of all ranges of arr2[] int prefix[] = new int[M + 1]; for (int i = 0; i < M + 1; i++) { prefix[i] = 0; } // Taking prefix sum for (int i = 1; i <= M; i++) { prefix[i] = prefix[i - 1] + arr2[i - 1]; } for (int i = 1; i <= N; i++) { // Add element i of arr1[] with range of // elements of arr2[] from l to r int r = Math.min(i, M); int l = Math.max(1, M - N + i); // Every element 'i' of arr1[] will // have sum of elements of arr2[] from // max(1, M - N + i) to min(i, M-1) which // can be calculate using prefix // sum in constant time arr1[i - 1] = arr1[i - 1] + prefix[r] - prefix[l - 1]; } for (int i = 0; i < N; i++) { System.out.print(arr1[i] + " "); } } // Driver program public static void main(String args[]) { int arr1[] = { 1, 1, 1, 1, 1 }; int arr2[] = { 1, 1, 1 }; int N = arr1.length; int M = arr2.length; // Function call addArr2ToArr1(arr1, arr2, N, M); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code to implement the approachdef addArr2toArr1(arr1, arr2, n, m): # Prefix sum array will be used # to store sum for all ranges of arr2[] prefix = [] for i in range(m+1): prefix.append(0) # Taking prefix sum for i in range(1, m+1): prefix[i] = prefix[i-1] + arr2[i-1] for i in range(1, n+1): # Add elements i of arr1 with range of # elements of arr2 from 1 to r r = int(min(i, m)) l = int(max(1, m-n+i)) # Every element 'i' of arr1 will # have sum of elements of arr2 from # max(1, m-n+1) to min(1, m-1) which # can be calculated using prefix # sum in constant time arr1[i-1] = arr1[i-1] + prefix[r] - prefix[l-1] for i in range(n): print(arr1[i], end=" ")arr1 = [1, 1, 1, 1, 1]arr2 = [1, 1, 1]# function calladdArr2toArr1(arr1, arr2, len(arr1), len(arr2)) |
C#
// C# code to implement the approachusing System;public class GFG { // Function to add corresponding // elements of arr2[] in all possible // subarrays of size M of arr1[] static void addArr2ToArr1(int[] arr1, int[] arr2, int N, int M) { // Prefix sum array will be used // to store sum of all ranges of arr2[] int[] prefix = new int[M + 1]; for (int i = 0; i < M + 1; i++) { prefix[i] = 0; } // Taking prefix sum for (int i = 1; i <= M; i++) { prefix[i] = prefix[i - 1] + arr2[i - 1]; } for (int i = 1; i <= N; i++) { // Add element i of arr1[] with range of // elements of arr2[] from l to r int r = Math.Min(i, M); int l = Math.Max(1, M - N + i); // Every element 'i' of arr1[] will // have sum of elements of arr2[] from // max(1, M - N + i) to min(i, M-1) which // can be calculate using prefix // sum in constant time arr1[i - 1] = arr1[i - 1] + prefix[r] - prefix[l - 1]; } for (int i = 0; i < N; i++) { Console.Write(arr1[i] + " "); } } static public void Main() { // Code int[] arr1 = { 1, 1, 1, 1, 1 }; int[] arr2 = { 1, 1, 1 }; int N = arr1.Length; int M = arr2.Length; // Function call addArr2ToArr1(arr1, arr2, N, M); }}// This code is contributed by lokeshmvs21. |
Javascript
function addArr2toArr1(arr1, arr2, n, m) { // Prefix sum array will be used // to store sum for all ranges of arr2[] var prefix = []; for (var i = 0; i <= m; i++) { prefix.push(0); } // Taking prefix sum for (var i = 1; i <= m; i++) { prefix[i] = prefix[i - 1] + arr2[i - 1]; } for (var i = 1; i <= n; i++) { // Add elements i of arr1 with range of // elements of arr2 from 1 to r var r = Math.min(i, m); var l = Math.max(1, m - n + i); // Every element 'i' of arr1 will // have sum of elements of arr2 from // max(1, m-n+1) to min(1, m-1) which // can be calculated using prefix // sum in constant time arr1[i - 1] = arr1[i - 1] + prefix[r] - prefix[l - 1]; } for (var i = 0; i < n; i++) { console.log(arr1[i]); }}var arr1 = [1, 1, 1, 1, 1];var arr2 = [1, 1, 1];// function calladdArr2toArr1(arr1, arr2, arr1.length, arr2.length); |
Output
2 3 4 3 2
Time Complexity: O(M + N)
Auxiliary Space: O(M)
Related Articles:
- Introduction to Arrays – Data Structure and Algorithm Tutorials
- Prefix Sum Array – Implementation and Applications in Competitive Programming
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!