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.

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.

Frequency Count Array

A Frequency Count Array is an array whose indexes are all the possible whole number values of another array, the given array (or given string). This means that the given array might have fewer or more values (elements), with some elements repeating (even more than twice). On the other hand, each of the element values of the Frequency Count Array, is either 0 or above 0, depending on whether its index occurs at least once, as value, in the given array. A value in the Frequency Count Array is the number of occurrences (frequency) of its index, as value, in the given array.

The Frequency Count Array has a fixed size, whose indexes are all the possible whole numbers that can be values in the given array. The given array can be shorter or same or longer than the Frequency Count Array, but the given array has a maximum value of interest (m). If it is shorter, it means some indexes of the Frequency Count Array are absent as values, in the given array. If it is the same, it might mean that some indexes of the Frequency Count Array are absent as values in the given array and some indexes of the Frequency Count Array repeat as values, in the given array; or each index in the Frequency Count Array occurs only once in the given array. If it is longer, it might mean that some indexes of the Frequency Count Array are absent as values in the given array, and some indexes of the Frequency Count Array repeat as values, in the given array; or each index in the Frequency Count Array is present at least once, in the given array, as value.

Problem

Given an array A[] consisting of N integers, the task is to find the total number of subsequences, which contain only one distinct number repeated throughout the subsequence. Consider an integer that occurs only once in the given array, as a repeat of one.

Examples:

Input: A[] = {1, 2, 1, 5, 2}
Output: 7
Explanation:
Subsequences {1}, {2}, {1}, {5}, {2}, {1, 1} and {2, 2} satisfy the required conditions.

Input: A[] = {5, 4, 4, 5, 10, 4}
Output: 11
Explanation:
Subsequences {5}, {4}, {4}, {5}, {10}, {4}, {5, 5}, {4, 4}, {4, 4}, {4, 4} and {4, 4, 4} satisfy the required conditions. The different positions of an integer that occurs more than once, in the given array, matters.

Frequency

- For either example above, if an element occurs once in its whole given array, its frequency in that array is 1.
- For either example above, if an element occurs twice in its whole given array, its frequency in that array is 2.
- For either example above, if an element occurs three times in its whole given array, its frequency in that array is 3.
- and so on.

Observation

Consider the following array:

[x, x, x, x]

There are 4 of the same element, x in the array. The frequency, f of x is 4. The different subsequences of this given array are:

[x], [x], [x], [x], [x,x], [x,x],[x,x], [x,x], [x,x], [x,x], [x,x,x], [x,x,x], [x,x,x], [x,x,x], [x,x,x,x]

which takes into consideration the position of each x in the given array.

The number of subsequences from the given array of 4 x's is

    15 = 16 -1 = 24 - 1

Power

If f = 1, then

       21 = 2

as an example of power expression. 2 is called the base and f=1 is called the exponent.

If f = 2, then

       22 = 2 x 2 = 4

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

If f = 3, then

       23 = 2 x 2 x 2 = 8

as an example of power expression. 2 is called the base and f=3 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.

Math Relationship between an Element's Frequency and its Number of Subsequences

In general, for a given array with mixed elements, the number of different subsequences produced by a repeated element, ignoring the empty subsequence, whether dispersed within the given array or not, is:

    number = 2f - 1 

If the empty subsequence is not ignored, the formula is:

    number = 2f 

In the program below, the empty subsequence is ignored.

So, for f = 1,

    number = 21 - 1 = 2 - 1 = 1

For frequency, f of 2,

    number = 22 - 1 = 4 - 1 = 3

For frequency of 3,

    number = 23 - 1 = 8 - 1 = 7

and so on.

Strategy

The aim is to find (count) the total number of subsequences produced by repeating elements in the given array. An element that occurs only once in the given array, repeats once. Do not forget to take into consideration, the positions of a repeating particular element in the given array.

Iterate through the given array while creating a frequency-count-array. For the second example above, the given array is:

    {5, 4, 4, 5, 10, 4} 

and the frequency-count-array is:

    {0, 0, 0, 0, 3, 2, 0, 0, 0, 0, 1}

4 occurs 3 times in the given array with frequency 3. So in the zero-based-indexed frequency count array, the position of index 4 has 3. Five occurs 2 times in the given array with frequency 2. So in the zero-based-indexed frequency count array, the position of index 5 has 2. Ten occurs 1 time in the given array with frequency 1. So in the zero-based-indexed frequency count array, the position of index 10 has 1.

The number of elements in the frequency count array is m+1, where m is the biggest number in the given array. The +1 is for the preceding zero, because an integer in the given array can be 0.

After iterating through the given array and created the frequency-count-array, iterate through the frequency-count-array.

While iterating through the frequency-count-array, note the frequencies (number of occurrences of each element) greater than 0.

For each of such frequencies, determine the number of subsequences it produces using the formula:

    number = 2f - 1 

Add all the numbers (answers) of such frequencies that are greater than 0.

All the above calculations should be done as the frequency-count-array is iterated through.

So, for the second example above, the result will be:

Output: 11 = (2^f - 1) + (2^f - 1) + (2^f - 1) = (2³ - 1) + (2² – 1) + (2¹ - 1) = (8 - 1) + (4 – 1) + (2 - 1) = (7) + (3) + (1) = 11

Efficient Program

An efficient program is according to the above strategy.

Efficient Program in O(n) Time

The efficient program is (read through the code and comments):

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

double totSubSeqRepeat(int A[], int n, int m) {

    int frequencyCountArray[m];
    for (int i=0; i <= m; i++)    //initializing frequencyCountArray with zeros
        frequencyCountArray[i] = 0; 

    for (int i = 0; i < n; i++) {    //updating from A[i]
        frequencyCountArray[A[i]] = frequencyCountArray[A[i]] + 1;
    } 

    double result = 0.0; 
    for (int i = 0; i <= m; i++) {    //summing required subsequences 
        result = result + pow(2, frequencyCountArray[i]) - 1; 
    }

    return result;
}

int main(int argc, char **argv) {
    int A[] = {5, 4, 4, 5, 10, 4};
    int n = sizeof(A) / sizeof(A[0]);
    
    int m = 0;
    for (int i=0; i < n; i++) {  //look for biggest element in given array
        if (A[i] > m)
            m = A[i];
    }
    
    double ret = totSubSeqRepeat(A, n, m);
    printf("%lf\n", ret);
    
    return 0;
}

The output is:

    11.000000

which is the same as 11, for this problem.

If only the two loops in the totSubSeqRepeat() function, without the initialization loop, are taken into consideration, then the time complexity would be O(n+m), where n is the length of the given array and m is the length of the frequency-count-array. The loop to determine m and the loop to initialze the frequencyCountArray are usually ignored. Remember that time complexity and space complexity are estimates.

However, the expression "pow(base, exponent)" alone in the frequency-count-array for-loop iteration, has a few number of time consuming operations. So the time complexity for the called function is given as:

    O(n.log2n)

which is usually longer than O(n+m) in many test cases.

The space complexity is O(n+m), where n is the length of the given array in the calling and called functions, and m is the length of the frequencyCountArray (actually m+1). Any extra space used is ignored.

Thanks for reading.