Given two arrays arr[] containing N integers and a mask[] of an odd size. The task is to replace every array element with the value computed by performing the same convolution on the array.
Examples:
Input: arr[] = {9, 7, 3, 9, 1, 8, 11}, mask[]={1, 2, -1}
Output: 11 20 4 20 3 6 30
Explanation: Following are the operations performed in the given array arr[]
For index 0: 0*1 + 9*2 + 7*-1 = 11
For index 1: 9*1 + 7*2 + 3*-1 = 20
For index 2: 7*1 + 3*2 + 9*-1 = 4
For index 3: 3*1 + 9*2 + 1*-1 = 20
For index 4: 9*1 + 1*2 + 8*-1 = 3
For index 5: 1*1 + 8*2 + 11*-1 = 6
For index 6: 8*1 + 11*2 + 0*-1 = 30Input: arr[] = {13, 26, 35, 41, 23, 18, 38}, mask[]={-1, 3, 5, -3, 1}
Output: 240 117 140 233 187 4 221
Approach: The simplest approach to solve this problem is to use nested loops. The outer loop will traverse the array from left to right, i.e. from i = 0 to i < N, and an inner loop will traverse the mask from index i – K/2 to the index i + K/2 and calculate the convolution of them. Finally, print the output.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to perform same convolutionvoid ComputeSameConvolution(int arr[], int mask[], int N, int K){ int i, j, k, sum; // Nested loops for (i = 0; i < N; i++) { sum = 0; k = 0; for (j = i - (K / 2); j <= i + (K / 2); j++) { if (j < 0 || j >= N) k++; else sum += arr[j] * mask[k++]; } // Print the required sum cout << sum << ' '; }}// Driver Codeint main(){ int arr[] = { 9, 7, 3, 9, 1, 8, 11 }; int mask[] = { 1, 2, -1 }; int K = sizeof(mask) / sizeof(mask[0]); int N = sizeof(arr) / sizeof(arr[0]); // Function Call ComputeSameConvolution(arr, mask, N, K); return 0;} |
Java
// Java program for the above approachclass GFG { // Function to perform same convolution static void ComputeSameConvolution(int[] arr, int[] mask, int N, int K) { int i, j, k, sum; // Nested loops for (i = 0; i < N; i++) { sum = 0; k = 0; for (j = i - (K / 2); j <= i + (K / 2); j++) { if (j < 0 || j >= N) k++; else sum += arr[j] * mask[k++]; } // Print the required sum System.out.print(sum + " "); } } // Driver Code public static void main(String[] args) { int[] arr = { 9, 7, 3, 9, 1, 8, 11 }; int[] mask = { 1, 2, -1 }; int K = mask.length; int N = arr.length; // Function Call ComputeSameConvolution(arr, mask, N, K); }}// This code is contributed by ukasp. |
Python3
# Python code for the above approach # Function to perform same convolutiondef ComputeSameConvolution(arr, mask, N, K): i = None j = None k = None sum = None # Nested loops for i in range(N): sum = 0; k = 0; for j in range(i - (K // 2), i + (K // 2) + 1): if (j < 0 or j >= N): k += 1 else: sum += arr[j] * mask[k]; k += 1 # Print the required sum print(sum, end=' ');# Driver Codearr = [9, 7, 3, 9, 1, 8, 11];mask = [1, 2, -1];K = len(mask)N = len(arr)# Function CallComputeSameConvolution(arr, mask, N, K);# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{// Function to perform same convolutionstatic void ComputeSameConvolution(int []arr, int []mask, int N, int K){ int i, j, k, sum; // Nested loops for (i = 0; i < N; i++) { sum = 0; k = 0; for (j = i - (K / 2); j <= i + (K / 2); j++) { if (j < 0 || j >= N) k++; else sum += arr[j] * mask[k++]; } // Print the required sum Console.Write(sum + " "); }}// Driver Codepublic static void Main(){ int []arr = { 9, 7, 3, 9, 1, 8, 11 }; int []mask = { 1, 2, -1 }; int K = mask.Length; int N = arr.Length; // Function Call ComputeSameConvolution(arr, mask, N, K);}}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to perform same convolution function ComputeSameConvolution(arr, mask, N, K) { let i, j, k, sum; // Nested loops for (i = 0; i < N; i++) { sum = 0; k = 0; for (j = i - Math.floor(K / 2); j <= i + Math.floor(K / 2); j++) { if (j < 0 || j >= N) k++; else sum += arr[j] * mask[k++]; } // Print the required sum document.write(sum + ' '); } } // Driver Code let arr = [9, 7, 3, 9, 1, 8, 11]; let mask = [1, 2, -1]; let K = mask.length; let N = arr.length; // Function Call ComputeSameConvolution(arr, mask, N, K); // This code is contributed by Potta Lokesh </script> |
11 20 4 20 3 6 30
Time Complexity: O(N*K)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
