Subarrays And Its Related Problems

Introduction

There are different ways to represent a part of the array. Some of them are given below:-

Subarray: A subarray is a contiguous part of array (i.e., occupying consecutive positions) that keeps the order of the elements intact.

For example: Consider the array A = [1,2,3]

There are 6 possible non-empty subarrays of A.

Subarrays are: [1], [2], [3], [1,2], [2,3], and [1,2,3].

Note: In general, there are n*(n+1)/2 non-empty subarrays for an array of size n.

Subsequence: A subsequence is a sequence that can be created by eliminating zero or more elements from another sequence while maintaining the order of the remaining elements.

For example: Consider the Array A = [1,2,3]

There are 7 possible non-empty subsequences of A.

Subsequences are: [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].

Note: In general, there are 2^n-1 non-empty subsequences for an array of size n.

Subset: Any possible combination of the original set is a subset. A subsequence is frequently referred to as a subset, although this is incorrect. A subsequence always keeps the array members in their relative order (i.e., increasing index), but a subset has no such restriction. [3,1] is a valid subset of [1, 2, 3]; however, it is not a subsequence or a subarray.

For example: Consider the Array A = [1,2,3]

Some of the Subsets of A are: [1], [2], [3], [1,3], [3,1], [1,2], etc.

In this blog, we will solve a programming problem related to Subarrays.

Problem Statement

Problem Name: Subarray Sum Divisible by K

We have an array of integers of size n and a positive integer k. Return the number of non-empty subarrays whose sum is divisible by k.

A subarray is a contiguous part of an array.

Examples:

Example1:-

Input: A = [1, -5, 5, 10] and k = 5

Output: 5

The non-empty subarrays whose sum are divisible by 5 are: [-5], [5], [10], [-5, 5], and [-5, 5, 10].

Example2:-

Input: A = [4, 7] and k = 6

Output: 0

There are no non-empty subarrays whose sum are divisible by 6.

Solution

1.) Brute Force:

We can run two for-loops to generate all the possible non-empty subarrays, and we can keep a variable to keep the sum of subarrays each time we iterate through the inner loop. If the sum is divisible by k, we will increase our answer count by one.

Code Implementation:

int subArraySumDivisibleByK(vector<int> &arr, int n, int k)

{

int subarray_count = 0;

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

int sum=0;

for(int j=i;j<n;j++){

sum+=arr[j];

if(sum%k==0) subarray_count++;

}

}

return subarray_count;

}

//Driver Code

int main(){

int n;

cin>>n;

vector<int>arr(n);

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

cin>>arr[i];

}

int k;

cin>>k;

int ans = subArraySumDivisibleByK(arr,n,k);

cout<<"Total number of Subarrays whose sum are divisible by k are: "<<ans<<endl;

return 0;

}

Time Complexity: O(N^2), since we are running two for-loops N times the time complexity will be quadratic.

Space Complexity: O(1), since we are not using any extra vector/array to store elements.

2.) Optimised Approach

In this approach, we will use Prefix Sum Array and count it to solve the problem in one pass.

A subarray must be a multiple of k if it is divisible by k.

a-b=n*k, where a is the running total and b is the sum of any previous subarray.

We need to find b, thus we'll use basic algebra: b=a-n*k.

We don't know what n is, so we can get rid of it by multiplying every element by k

(b % k) = (a % k) - (n*k) % k

Since n*k is a multiple of k and k goes into it evenly, the result of the (n *k) % k will be 0, so b % k = a % k is the same as the formula we defined earlier, a-b=n*k.

So all we have to do now is compare the current total mod k to any previous running total mod k.

Code Implementation:

int subArraySumDivisibleByK(vector<int> &arr, int n, int k)

{

vector<int>count(k);

count[0] = 1;

int prefix = 0, subarray_count = 0;

for (int x : arr) {

prefix = (prefix + x % k + k) % k; //x % k + k takes care of the cases where x < 0.

subarray_count += count[prefix]++;

}

return subarray_count;

}

//Driver Code

int main(){

int n;

cin>>n;

vector<int>arr(n);

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

cin>>arr[i];

}

int k;

cin>>k;

int ans = subArraySumDivisibleByK(arr,n,k);

cout<<"Total number of Subarrays whose sum are divisible by k are: "<<ans<<endl;

return 0;

}

Time Complexity: O(N), since we are running only one for-loop N times, the time complexity is linear.

Space Complexity: O(K), since we are using a vector of length K to store our prefix sum the space complexity is also linear and varies according to K.