Given a positive integer N. Count the total number of ordered sets of any size such that consecutive numbers are not present in the set and all numbers are <= N.
Ordered Set: Arrays in which all numbers are distinct, and order of elements is taken into consideration, For e.g. {1, 2, 3} is different from {1, 3, 2}.
Examples:
Input: N = 3
Output: 5
Explanation:
The ordered sets are:
{1}, {2}, {3}, {1, 3}, {3, 1}Input: N = 6
Output: 50
Naive Approach:
- We will use Recursion to solve this problem. If we obtain a count say C of the ordered set where elements are in ascending/descending order and the set size is S, then total count for this size will
- We will do this for each ordered set of distinct sizes.
- Iterate on all ordered set sizes and for each size find the count of ordered sets and multiply by factorial of size ( S! ). At each recursive step, we have two options –
- Include the current element x and move to the next position with maximum element that can be included now as x – 2.
- Do not include the current element x and stay at the current position with maximum element that can be included now as x – 1.
- So the recursive relation is :
countSets(x, pos) = countSets(x-2, pos-1) + countSets(x-1, pos)
C++
// C++ program to Count the number of // ordered sets not containing // consecutive numbers#include <bits/stdc++.h>using namespace std;// Function to calculate the count// of ordered set for a given sizeint CountSets(int x, int pos){ // Base cases if (x <= 0) { if (pos == 0) return 1; else return 0; } if (pos == 0) return 1; int answer = CountSets(x - 1, pos) + CountSets(x - 2, pos - 1); return answer;}// Function returns the count // of all ordered setsint CountOrderedSets(int n){ // Prestore the factorial value int factorial[10000]; factorial[0] = 1; for (int i = 1; i < 10000; i++) factorial[i] = factorial[i - 1] * i; int answer = 0; // Iterate all ordered set sizes and find // the count for each one maximum ordered // set size will be smaller than N as all // elements are distinct and non consecutive for (int i = 1; i <= n; i++) { // Multiply ny size! for all the // arrangements because sets are ordered int sets = CountSets(n, i) * factorial[i]; // Add to total answer answer = answer + sets; } return answer;}// Driver codeint main(){ int N = 3; cout << CountOrderedSets(N); return 0;} |
Java
// Java program to count the number // of ordered sets not containing // consecutive numbersclass GFG{// Function to calculate the count// of ordered set for a given sizestatic int CountSets(int x, int pos){ // Base cases if (x <= 0) { if (pos == 0) return 1; else return 0; } if (pos == 0) return 1; int answer = CountSets(x - 1, pos) + CountSets(x - 2, pos - 1); return answer;}// Function returns the count // of all ordered setsstatic int CountOrderedSets(int n){ // Prestore the factorial value int []factorial = new int[10000]; factorial[0] = 1; for(int i = 1; i < 10000; i++) factorial[i] = factorial[i - 1] * i; int answer = 0; // Iterate all ordered set sizes and find // the count for each one maximum ordered // set size will be smaller than N as all // elements are distinct and non consecutive for(int i = 1; i <= n; i++) { // Multiply ny size! for all the // arrangements because sets are ordered int sets = CountSets(n, i) * factorial[i]; // Add to total answer answer = answer + sets; } return answer;}// Driver codepublic static void main(String[] args){ int N = 3; System.out.print(CountOrderedSets(N));}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to count the number of # ordered sets not containing # consecutive numbers# Function to calculate the count# of ordered set for a given sizedef CountSets(x, pos): # Base cases if (x <= 0): if (pos == 0): return 1 else: return 0 if (pos == 0): return 1 answer = (CountSets(x - 1, pos) + CountSets(x - 2, pos - 1)) return answer # Function returns the count # of all ordered setsdef CountOrderedSets(n): # Prestore the factorial value factorial = [1 for i in range(10000)] factorial[0] = 1 for i in range(1, 10000, 1): factorial[i] = factorial[i - 1] * i answer = 0 # Iterate all ordered set sizes and find # the count for each one maximum ordered # set size will be smaller than N as all # elements are distinct and non consecutive for i in range(1, n + 1, 1): # Multiply ny size! for all the # arrangements because sets are ordered sets = CountSets(n, i) * factorial[i] # Add to total answer answer = answer + sets return answer# Driver codeif __name__ == '__main__': N = 3 print(CountOrderedSets(N))# This code is contributed by Samarth |
C#
// C# program to count the number // of ordered sets not containing // consecutive numbersusing System;class GFG{// Function to calculate the count// of ordered set for a given sizestatic int CountSets(int x, int pos){ // Base cases if (x <= 0) { if (pos == 0) return 1; else return 0; } if (pos == 0) return 1; int answer = CountSets(x - 1, pos) + CountSets(x - 2, pos - 1); return answer;}// Function returns the count // of all ordered setsstatic int CountOrderedSets(int n){ // Prestore the factorial value int []factorial = new int[10000]; factorial[0] = 1; for(int i = 1; i < 10000; i++) factorial[i] = factorial[i - 1] * i; int answer = 0; // Iterate all ordered set sizes and find // the count for each one maximum ordered // set size will be smaller than N as all // elements are distinct and non consecutive for(int i = 1; i <= n; i++) { // Multiply ny size! for all the // arrangements because sets are ordered int sets = CountSets(n, i) * factorial[i]; // Add to total answer answer = answer + sets; } return answer;}// Driver codepublic static void Main(String[] args){ int N = 3; Console.Write(CountOrderedSets(N));}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program to count the number // of ordered sets not containing // consecutive numbers // Function to calculate the count// of ordered set for a given size function CountSets(x , pos) { // Base cases if (x <= 0) { if (pos == 0) return 1; else return 0; } if (pos == 0) return 1; var answer = CountSets(x - 1, pos) + CountSets(x - 2, pos - 1); return answer; } // Function returns the count // of all ordered sets function CountOrderedSets(n) { // Prestore the factorial value var factorial = Array(10000).fill(0); factorial[0] = 1; for (i = 1; i < 10000; i++) factorial[i] = factorial[i - 1] * i; var answer = 0; // Iterate all ordered set sizes and find // the count for each one maximum ordered // set size will be smaller than N as all // elements are distinct and non consecutive for (i = 1; i <= n; i++) { // Multiply ny size! for all the // arrangements because sets are ordered var sets = CountSets(n, i) * factorial[i]; // Add to total answer answer = answer + sets; } return answer; } // Driver code var N = 3; document.write(CountOrderedSets(N));// This code contributed by umadevi9616 </script> |
Output:
5
Time Complexity: O(2N)
Efficient Approach:
- In the recursive approach, we are solving subproblems multiple times, i.e. it follows the Overlapping Subproblems Property in Dynamic Programming. So we can use a memorization table or cache to make the solution efficient.
C++
// C++ program to Count the number // of ordered sets not containing // consecutive numbers#include <bits/stdc++.h>using namespace std;// DP tableint dp[500][500];// Function to calculate the count// of ordered set for a given sizeint CountSets(int x, int pos){ // Base cases if (x <= 0) { if (pos == 0) return 1; else return 0; } if (pos == 0) return 1; // If subproblem has been // solved before if (dp[x][pos] != -1) return dp[x][pos]; int answer = CountSets(x - 1, pos) + CountSets(x - 2, pos - 1); // Store and return answer to // this subproblem return dp[x][pos] = answer;}// Function returns the count // of all ordered setsint CountOrderedSets(int n){ // Prestore the factorial value int factorial[10000]; factorial[0] = 1; for (int i = 1; i < 10000; i++) factorial[i] = factorial[i - 1] * i; int answer = 0; // Initialise the dp table memset(dp, -1, sizeof(dp)); // Iterate all ordered set sizes and find // the count for each one maximum ordered // set size will be smaller than N as all // elements are distinct and non consecutive. for (int i = 1; i <= n; i++) { // Multiply ny size! for all the // arrangements because sets // are ordered. int sets = CountSets(n, i) * factorial[i]; // Add to total answer answer = answer + sets; } return answer;}// Driver codeint main(){ int N = 3; cout << CountOrderedSets(N); return 0;} |
Java
// Java program to count the number // of ordered sets not containing // consecutive numbersimport java.util.*;class GFG{// DP tablestatic int [][]dp = new int[500][500];// Function to calculate the count// of ordered set for a given sizestatic int CountSets(int x, int pos){ // Base cases if (x <= 0) { if (pos == 0) return 1; else return 0; } if (pos == 0) return 1; // If subproblem has been // solved before if (dp[x][pos] != -1) return dp[x][pos]; int answer = CountSets(x - 1, pos) + CountSets(x - 2, pos - 1); // Store and return answer to // this subproblem return dp[x][pos] = answer;}// Function returns the count // of all ordered setsstatic int CountOrderedSets(int n){ // Prestore the factorial value int []factorial = new int[10000]; factorial[0] = 1; for(int i = 1; i < 10000; i++) factorial[i] = factorial[i - 1] * i; int answer = 0; // Initialise the dp table for(int i = 0; i < 500; i++) { for(int j = 0; j < 500; j++) { dp[i][j] = -1; } } // Iterate all ordered set sizes and find // the count for each one maximum ordered // set size will be smaller than N as all // elements are distinct and non consecutive. for(int i = 1; i <= n; i++) { // Multiply ny size! for all the // arrangements because sets // are ordered. int sets = CountSets(n, i) * factorial[i]; // Add to total answer answer = answer + sets; } return answer;}// Driver codepublic static void main(String[] args){ int N = 3; System.out.print(CountOrderedSets(N));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to count the number # of ordered sets not containing # consecutive numbers# DP tabledp = [[-1 for j in range(500)] for i in range(500)] # Function to calculate the count# of ordered set for a given sizedef CountSets(x, pos): # Base cases if (x <= 0): if (pos == 0): return 1 else: return 0 if (pos == 0): return 1 # If subproblem has been # solved before if (dp[x][pos] != -1): return dp[x][pos] answer = (CountSets(x - 1, pos) + CountSets(x - 2, pos - 1)) # Store and return answer to # this subproblem dp[x][pos] = answer return answer# Function returns the count # of all ordered setsdef CountOrderedSets(n): # Prestore the factorial value factorial = [0 for i in range(10000)] factorial[0] = 1 for i in range(1, 10000): factorial[i] = factorial[i - 1] * i answer = 0 # Iterate all ordered set sizes and find # the count for each one maximum ordered # set size will be smaller than N as all # elements are distinct and non consecutive. for i in range(1, n + 1): # Multiply ny size! for all the # arrangements because sets # are ordered. sets = CountSets(n, i) * factorial[i] # Add to total answer answer = answer + sets return answer# Driver codeif __name__=="__main__": N = 3 print(CountOrderedSets(N))# This code is contributed by rutvik_56 |
C#
// C# program to count the number // of ordered sets not containing // consecutive numbersusing System;class GFG{// DP tablestatic int [,]dp = new int[500, 500];// Function to calculate the count// of ordered set for a given sizestatic int CountSets(int x, int pos){ // Base cases if (x <= 0) { if (pos == 0) return 1; else return 0; } if (pos == 0) return 1; // If subproblem has been // solved before if (dp[x,pos] != -1) return dp[x, pos]; int answer = CountSets(x - 1, pos) + CountSets(x - 2, pos - 1); // Store and return answer to // this subproblem return dp[x, pos] = answer;}// Function returns the count // of all ordered setsstatic int CountOrderedSets(int n){ // Prestore the factorial value int []factorial = new int[10000]; factorial[0] = 1; for(int i = 1; i < 10000; i++) factorial[i] = factorial[i - 1] * i; int answer = 0; // Initialise the dp table for(int i = 0; i < 500; i++) { for(int j = 0; j < 500; j++) { dp[i, j] = -1; } } // Iterate all ordered set sizes and find // the count for each one maximum ordered // set size will be smaller than N as all // elements are distinct and non consecutive. for(int i = 1; i <= n; i++) { // Multiply ny size! for all the // arrangements because sets // are ordered. int sets = CountSets(n, i) * factorial[i]; // Add to total answer answer = answer + sets; } return answer;}// Driver codepublic static void Main(String[] args){ int N = 3; Console.Write(CountOrderedSets(N));}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// JavaScript program to Count the number // of ordered sets not containing // consecutive numbers// DP tablevar dp = Array.from(Array(500), ()=>Array(500));// Function to calculate the count// of ordered set for a given sizefunction CountSets(x, pos){ // Base cases if (x <= 0) { if (pos == 0) return 1; else return 0; } if (pos == 0) return 1; // If subproblem has been // solved before if (dp[x][pos] != -1) return dp[x][pos]; var answer = CountSets(x - 1, pos) + CountSets(x - 2, pos - 1); // Store and return answer to // this subproblem return dp[x][pos] = answer;}// Function returns the count // of all ordered setsfunction CountOrderedSets(n){ // Prestore the factorial value var factorial = Array(10000).fill(0); factorial[0] = 1; for (var i = 1; i < 10000; i++) factorial[i] = factorial[i - 1] * i; var answer = 0; // Initialise the dp table dp = Array.from(Array(500), ()=>Array(500).fill(-1)); // Iterate all ordered set sizes and find // the count for each one maximum ordered // set size will be smaller than N as all // elements are distinct and non consecutive. for (var i = 1; i <= n; i++) { // Multiply ny size! for all the // arrangements because sets // are ordered. var sets = CountSets(n, i) * factorial[i]; // Add to total answer answer = answer + sets; } return answer;}// Driver codevar N = 3;document.write( CountOrderedSets(N));</script> |
Output:
5
Time Complexity: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
