Home » Interview coding problems/challenges

Count the number of elements which are greater than previous element

Here, we are going to learn how to count the number of elements which are greater than previous element using the recursion approach?
Submitted by Souvik Saha, on June 26, 2020

Problem statement:

Given a range 1 to N. Among its different permutations you have to find out those permutations where only one element is greater than its previous element and you have to count that number.

For numbers 1 to 3, there are several permutations,

1 2 3       1 2 && 2 3
1 3 2       1 3
2 1 3       1 3
2 3 1       2 3
3 1 2       1 2
3 2 1       none

Input:
T no.of Testcases.
T no. Of lines along with the N values with it.

E.g.
3
2
3
4

Constrains:
1 ≤ T ≤ 10
1≤ N ≤ 9

Output:
Print the count of the permutations 
those have only one element is greater than 
the previous one.

Example

T=3

Input:
N=2

Output:
1 2 
Count: 1

Input:
N=3

Output:
1 3 2 
2 1 3 
2 3 1 
3 1 2 
Count: 4

Input:
N=4

Output:
1 4 3 2 
2 1 4 3 
2 4 3 1 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 2 1 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
Count: 11

Explanation with example:

Let the range is N. Therefore, the numbers are X₁, X₂, X₃, ..., X_N.

Let f(i) = select an element in the permutation.

To know which elements are already visited in the array we will use a Boolean array and store the permutations we will use another array.

To find out the permutations we will follow these following steps,

1. We traverse the whole array and pick the first non-visited element from the array.
2. Compare the current none visited element with the last element of the second array. If the last element is less than the current element, we will increase the counter value otherwise not.
3. After the checking, we insert the current element into the second array.
4. Repeat step 1 to step 3 until we traverse the whole element of the array.
5. After traversing the whole array, we check the counter. If the count value equals to one then we will print the second array and consider that permutation into our count.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

void permutation(bool* visit, int* arr, int ran, int& count, int pos, vector<int> v, int g_count)
{
    if (pos >= ran) {
        if (g_count == 1) {
            count++;
            for (int i = 0; i < ran; i++) {
                cout << v[i] << " ";
            }
            cout << endl;
        }
        return;
    }
    for (int i = 0; i < ran; i++) {
        if (!visit[i]) {
            visit[i] = true;
            if (pos != 0) {
                if (v[pos - 1] < arr[i]) {
                    g_count++;
                }
            }
            v.push_back(arr[i]);
            permutation(visit, arr, ran, count, pos + 1, v, g_count);
            v.pop_back();
            visit[i] = false;
            if (pos != 0) {
                if (v[pos - 1] < arr[i]) {
                    g_count--;
                }
            }
        }
    }
}

int main()
{
    int t;
    cout << "Test Case : ";
    cin >> t;
    while (t--) {
        int ran;
        cout << "Enter the range : ";
        cin >> ran;
        int arr[ran];
        int count = 1;
        for (int i = 0; i < ran; i++) {
            arr[i] = count;
            count++;
        }
        bool visit[ran] = { false };
        count = 0;
        int pos = 0, g_count = 0;
        vector<int> v;
        permutation(visit, arr, ran, count, pos, v, g_count);
        cout << "Count : " << count << endl;
    }
    
    return 0;
}

Output

Test Case : 3
Enter the range : 2
1 2
Count : 1
Enter the range : 3
1 3 2
2 1 3
2 3 1
3 1 2
Count : 4
Enter the range : 4
1 4 3 2
2 1 4 3
2 4 3 1
3 1 4 2
3 2 1 4
3 2 4 1
3 4 2 1
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
Count : 11