×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

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 X1, X2, X3, ..., XN.

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


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.