Count the number of ordered sets not containing consecutive numbers

20 October 2023

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 $C * S!$
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 –
1. Include the current element x and move to the next position with maximum element that can be included now as x – 2.
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 size
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 sets
int 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 code
int main()
{
    int N = 3;
 
    cout << CountOrderedSets(N);
 
    return 0;
}

Java

// Java program to count the number  
// of ordered sets not containing 
// consecutive numbers
class GFG{
 
// Function to calculate the count
// of ordered set for a given size
static 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 sets
static 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 code
public 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 size
def 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 sets
def 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 code
if __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 numbers
using System;
class GFG{
 
// Function to calculate the count
// of ordered set for a given size
static 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 sets
static 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 code
public 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:

Time Complexity: O(2^N)

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 table
int dp[500][500];
 
// Function to calculate the count
// of ordered set for a given size
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 sets
int 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 code
int main()
{
    int N = 3;
 
    cout << CountOrderedSets(N);
 
    return 0;
}

Java

// Java program to count the number 
// of ordered sets not containing 
// consecutive numbers
import java.util.*;
 
class GFG{
 
// DP table
static int [][]dp = new int[500][500];
 
// Function to calculate the count
// of ordered set for a given size
static 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 sets
static 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 code
public 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 table
dp = [[-1 for j in range(500)]
          for i in range(500)]
  
# Function to calculate the count
# of ordered set for a given size
def 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 sets
def 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 code
if __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 numbers
using System;
class GFG{
 
// DP table
static int [,]dp = new int[500, 500];
 
// Function to calculate the count
// of ordered set for a given size
static 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 sets
static 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 code
public 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 table
var dp = Array.from(Array(500), ()=>Array(500));
 
// 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;
 
    // 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 sets
function 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 code
var N = 3;
document.write( CountOrderedSets(N));
 
 
</script>

Output:

Time Complexity: O(N²)

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!

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

LEAVE A REPLY