Consecutive Subsequences Solution

Problem Statement of Consecutive subsequences

You are given an array A of size n and an integer K. You have to count the number of consecutive subsequences of the array A whose elements’ sum is divisible by K. The original statement of Consecutive Subsequences challenge is available on Hackerrank.

What is Consecutive Subsequence?

First, let’s understand the subsequence. If we pick 1 or more elements of the array in such a way that the relative order of the elements remain same then it is called a subsequence of the given array. For instance, suppose the given array is A=[1, 5, 3, 2, 9, 7, 12]. We pick the elements [5, 2, 7, 12], then it is a subsequence of A because the elements [5, 2, 7, 12] are in the same order (not necessarily on contiguous positions) in the original array also.

In the above definition of if the subsequence can contain only the elements which are on contiguous positions then it becomes Consecutive subsequence. For instance, for A=[1, 5, 3, 2, 9, 7, 12], [3, 2, 9, 7] is a consecutive subsequence. [12] is another consecutive subsequence of A. [1, 5, 3, 12] is just a subsequence but not consecutive subsequence because 3 and 12 are not adjacent to each other.

Basic Approach by generating all consecutive subsequences ( O(n3))

The basic logic of generating all the consecutive subsequences of the array is to generate subsequences for all lengths starting from 1. The pseudo code is given as follows:

A[n]; // The given array. Suppose the indexing starts from 1
for( k = 1 to n)  // for Length of the subsequence
{
	for( i = 1 to (n-k-1) ) //for all subsequence of length k
	{
                             Print: \n; \ for new line
		for( j = i to (i +k-1) ) // This loop traverses the subsequence of length k
		{
			Print: A[j]; 
		}
	}
}

The above code takes roughly O(n^3) time. Instead of printing the elements of subsequence in the inner most loop (j loop) we can calculate sum of the elements and can check its divisibility by k as follows:

A[n]; // The given array. Suppose the indexing starts from 1
int countsub = 0;
int sum;
for( k = 1 to n)  // for Length of the subsequence
{
	for( i = 1 to (n-k-1) ) //for all subsequence of length k
	{
                             sum = 0; //for each subsequence
		for( j = i to (i +k-1) ) // This loop traverses the subsequence of length k
		{
			sum = sum + A[j];
		}
		if( sum % k == 0)
			countsub = countsub + 1;
	}
}
Print : countsub;

The above approach can be optimized to using cumulative sum.

Cumulative Sum Approach (O(n2))

If we calculate the cumulative sum of the given array A and store it in cumulative sum array C then the inner most loop (j loop) can be replaced by a constant time expression. For example,

C[0] = 0;
for( i = 1 to n)  
	C[i] = C[i-1] + A[i];
Consecutive Subsequences solution

Now, sum of the consecutive subsequence (i to j) can be calculated using following formula:

sum(i to j) = C[j] – C[i-1];

For instance, consider the subsequence (2 to 6) i.e. [5, 8, 7, 1, 9].

sum(2 to 6) = C[6] – C[1] = 33 – 3 = 30 ( = 5 + 8 + 7 + 1 + 9)

Using this phenomenon, the above approach can be improved as follows:

A[n]; // The given array. Suppose the indexing starts from 1
int countsub = 0;
for( k = 1 to n)  // for Length of the subsequence
{
i = 1;
	for( j = k to n ) // subsequence i to j
	{
		if( (C[j] – C[i-1]) % k == 0)
			countsub++;
		i++;
	}
}
Print : countsub;

This approach takes O(n2) time. It can be further improved to achieve linear time complexity (O(n)) as follows:

O(n) Approach to Solve Consecutive Subsequences

In the above approach, we calculate sum of elements in the consecutive subsequence i to j as C[j] – C[i-1]. Then we check the divisibility as (C[j] – C[i-1]) % k is equal to 0 or not. Let’s assume that the sum of elements in the consecutive subsequence i to j is divisible by k, then

(C[j] – C[i-1]) % k = 0
C[j] % k – C[i-1] % k = 0
C[j] % k = C[i-1] % k

The above derivation implies that if remainder of C[i-1] when divided by k is equal to remainder of C[j] when divided by k then i to j is a valid consecutive subsequence.

Now we don’t need actual cumulative sum but we need remainders. From cumulative sum array C we will calculate Remainder array R as follows ( assume k = 4):

for( i = 0 to n)
	R[i] = C[i]%k;
Consecutive Subsequences solutions

In the remainder array R, we should pick indexes having same remainders. For example, index 1 and index 7 has same remainder 3 so the subsequence 2 to 7 will be a valid subsequence because (C[j] – C[i-1]) % k will be equal to 0. Similar situation is for index 1 and 4 and for 4 and 7 also. So now we can say, we just have to make unordered pairs of indexes 1, 4 and 7 because all have same remainder. So the total valid subsequences is equal to number of ways of selecting any two out of n indexes having same remainder. Which is equal to nC2 = n(n-1)/2. So now we need the frequency of each remainder. Let’s construct the frequency array of remainders as follows:

for ( i = 0 to k-1)
	F[i] = 0;
for( i = 0 to n)
	F[ R[i] ] ++; 
Consecutive Subsequences Solution

nC2 for each remainder is calculated and added in countsub as follows:

countsub = 0;
for ( i = 0 to k-1)
	countsub = countsub + ( F[i] * (F[i] – 1) ) / 2;

Complete Pseudo Code for Consecutive Subsequences

A[n]; // The given array. Suppose the indexing starts from 1
C[n]; //For cumulative sum
R[n];//For remainders
F[k];//For frequencies of remainders 

int countsub = 0;
C[0] = 0;

for( i = 1 to n)  
	C[i] = C[i-1] + A[i];

for( i = 0 to n)
	R[i] = C[i]%k;

for ( i = 0 to k-1)
	F[i] = 0;

for( i = 0 to n)
	F[ R[i] ] ++; 

for( i = 0 to k-1)
	countsub = countsub + ( F[i] * (F[i] – 1) ) / 2;

Print: countsub;

This code runs in O(n) time.

Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *