The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

A Subsequence

A subsequence is a sequence that can be derived from an array or another sequence, by removing zero or more elements, without changing the order of the remaining elements. The subsequence maintains the order it had in the original array or original sequence.

In general, for the original sequence of size n, there can be up to (2ⁿ - 1) non-empty sub-sequences in total.

For example, in the array [1, 2, 3, 4], there are 15 non-empty sub-sequences, which are:

[1], [2], [3], [4], [1,2], [1,3],[1,4], [2,3], [2,4], [3,4], [1,2,3], [1,2,4], [1,3,4], [2,3,4], [1,2,3,4] .

This is the number of combinations, but maintaining the order of appearance in the given (original) array.

A complete (power set) of subsequences of any array includes the empty subsequence: []. With that, the total number of possible subsequences from the original array is 2ⁿ .

Even-number only type subsequences from the 15 subsequences above, are:

[2], [4], [2,4]

which are not up to half of the 15 subsequences constituting the whole set (of subsequences).

Odd-number only type subsequences from the 15 subsequences above, are:

[1], [3], [1,3]

which are not up to half of the 15 subsequences constituting the whole set (of subsequences).

Out of the whole set of possible subsequences, only one or more subsequences with a characteristic description, is usually required.

A Subarray

A subarray is a continuous part of an array. In other-words, a subarray is an array that is inside another array.

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

For example, in the array [1, 2, 3, 4], there are 10 non-empty sub-arrays, which are:

[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4]

A subarray differs from a subsequence, in that, the subarray is a continuous subset while the subsequence is not necessarily a continuous subset; and the subarray does not necessarily have a characteristic description.

Two Pointers Technique

Two pointers refer to left (i) and right (j) indexes, such that left points to the start of the array and right points to the end of the array, initially. The opposite pointers move towards the center of the array during iterations, until a condition is met.

A Sliding Window

A sliding window is a sub-array that moves from one end of the array to the other end, one element at a time. The left end of the window is typically identified by the variable, i or left or back. The right end of the window is typically identified by the variable, j or right or front.

As the window moves, its size (length) may be fixed or variable.

The sliding window is a specialized application of the two-pointers technique.

Problem

Given an integer N which denotes the length of an array, the task is to count the number of subarrays and subsequences possible with the given array.

Examples:

Input: N = 5
Output:
Count of subarray = 15
Count of subsequence = 32

Input: N = 3
Output:
Count of subarray = 6
Count of subsequence = 8

Strategy

Just apply the formula for number of subarrays of a given array, which is:

    n*(n+1)/2

where * means multiplication and the zero length subarray is not included. Also just apply the formula for number of subsequences of an array, which is:

       2n 

and includes the zero length subsequence.

If n = 4, then

       2n = 2 x 2 x 2 x 2 = 16

as an example of power expression. 2 is called the base and n is called the exponent.

In C programming, the power expression is:

    result = pow(base, exponent);

where the predefined function, pow() is from the math.h library and has to be included into the program.

The variables: base, exponent and result are all the double type.

Example,

    16.0 = pow(2.0, 4.0) = 24 = 2 x 2 x 2 x 2 = 16

Efficient Programs

Two programs are given below: one for number of subarrays and the other for number of subsequences.

The smart program for number of subarrays of an array is (read through the code and comments):

#include <stdio.h>

int noSubArrays(int n) {
    return n*(n + 1)/2;
}

int main(int argc, char **argv) {
    int n = 5;
    int ret = noSubArrays(n);
    printf("%i\n", ret);
    
    return 0;
}

The output is:

    15

as expected.

The time complexity for the algorithm is the constant time O(1), for the single formula, n*(n + 1)/2 . The space complexity is also O(1), though it is actually O(2) with O(1) for 5 in the calling function and O(1) for the copy of 5 in the called function.

The smart program for number of subsequences of an array is (read through the code and comments):

#include <stdio.h>
#include <math.h>

double noSubSequences(int n) {
    return pow(2, n);
}

int main(int argc, char **argv) {
    double n = 5;
    double ret = noSubSequences(n);
    printf("%lf\n", ret);
    
    return 0;
}

The output is:

    32.000000

which is the same as 32 .

The time complexity is O(log₂n) for the pow(2, n) predefined function. This will be explained later in the full course, with what is known as recursion. The space complexity will be explained later in the full course.

Thanks for reading.