Data Modelling & AI Data Structure & Algorithm

Count number of Special Set

23 June 2025

0

An ordered set of integers is said to be a special set if for every element of the set X, the set does not contain the element X + 1. Given an integer N, the task is to find the number of special sets whose largest element is not greater than N. Since, the number of special sets can be very large, print the answer modulo 10^{9 + 7}.
Example:

Input: N = 3
Output: 5
{1}, {2}, {3}, {1, 3} and {3, 1} are the
only special sets possible.
Input: N = 4
Output: 10

Approach: This problem can be solved using dynamic programming. Create an array dp[][] where dp[i][j] stores the number of special sets of length i ending with j. Now, the recurrence relation will be:

dp[i][j] = dp[i – 1][1] + dp[i – 1][2] + … + dp[i – 1][j – 2]
dp[i][j] can be computed in O(1) by taking the prefix sum of the previous dp[i – 1] once.

Now the total special sets of size i can be calculated by multiplying dp[i][n] with factorial(i).
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int MAX = 2 * 1000 + 10;
const int MOD = 1e9 + 7;
 
// To store the states of the dp
ll dp[MAX][MAX];
 
// Function to return (a + b) % MOD
ll sum(ll a, ll b)
{
    return ((a % MOD) + (b % MOD)) % MOD;
}
 
// Function to return (a * b) % MOD
ll mul(ll a, ll b)
{
    return ((a % MOD) * (b % MOD)) % MOD;
}
 
// Function to return the count
// of special sets
int cntSpecialSet(int n)
{
 
    // Fill the dp[][] array with the answer
    // for the special sets of size 1
    for (int i = 1; i <= n; i++) {
        dp[1][i] = 1;
 
        // Take prefix sum of the current row which
        // will be used to fill the next row
        dp[1][i] += dp[1][i - 1];
    }
 
    // Fill the rest of the dp[][] array
    for (int i = 2; i <= n; i++) {
 
        // Recurrence relation
        for (int j = 2; j <= n; j++) {
            dp[i][j] = dp[i - 1][j - 2];
        }
 
        // Calculate the prefix sum
        for (int j = 1; j <= n; j++) {
            dp[i][j] = sum(dp[i][j], dp[i][j - 1]);
        }
    }
 
    ll ways(1), ans(0);
 
    for (int i = 1; i <= n; i++) {
 
        // To find special set of size i
        ways = mul(ways, i);
 
        // Addition of special sets of all sizes
        ans = sum(ans, mul(ways, dp[i][n]));
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int n = 3;
 
    cout << cntSpecialSet(n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG 
{
static int MAX = 2 * 1000 + 10;
static int MOD = (int) (1e9 + 7);
 
// To store the states of the dp
static long [][]dp = new long[MAX][MAX];
 
// Function to return (a + b) % MOD
static long sum(long a, long b)
{
    return ((a % MOD) + (b % MOD)) % MOD;
}
 
// Function to return (a * b) % MOD
static long mul(long a, long b)
{
    return ((a % MOD) * (b % MOD)) % MOD;
}
 
// Function to return the count
// of special sets
static long cntSpecialSet(int n)
{
 
    // Fill the dp[][] array with the answer
    // for the special sets of size 1
    for (int i = 1; i <= n; i++) 
    {
        dp[1][i] = 1;
 
        // Take prefix sum of the current row which
        // will be used to fill the next row
        dp[1][i] += dp[1][i - 1];
    }
 
    // Fill the rest of the dp[][] array
    for (int i = 2; i <= n; i++) 
    {
 
        // Recurrence relation
        for (int j = 2; j <= n; j++) 
        {
            dp[i][j] = dp[i - 1][j - 2];
        }
 
        // Calculate the prefix sum
        for (int j = 1; j <= n; j++) 
        {
            dp[i][j] = sum(dp[i][j], dp[i][j - 1]);
        }
    }
 
    long ways = 1, ans = 0;
  
    for (int i = 1; i <= n; i++) 
    {
 
        // To find special set of size i
        ways = mul(ways, i);
 
        // Addition of special sets of all sizes
        ans = sum(ans, mul(ways, dp[i][n]));
    }
 
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 3;
 
    System.out.println(cntSpecialSet(n));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach
 
# Function to print the nodes having 
# maximum and minimum degree 
def minMax(edges, leng, n) : 
 
    # Map to store the degrees of every node 
    m = {};
     
    for i in range(leng) :
        m[edges[i][0]] = 0;
        m[edges[i][1]] = 0;
         
    for i in range(leng) :
         
        # Storing the degree for each node
        m[edges[i][0]] += 1;
        m[edges[i][1]] += 1; 
 
    # maxi and mini variables to store 
    # the maximum and minimum degree 
    maxi = 0; 
    mini = n; 
 
    for i in range(1, n + 1) :
        maxi = max(maxi, m[i]); 
        mini = min(mini, m[i]); 
 
    # Printing all the nodes 
    # with maximum degree 
    print("Nodes with maximum degree : ", 
                                end = "")
     
    for i in range(1, n + 1) :
        if (m[i] == maxi) :
            print(i, end = " "); 
 
    print()
 
    # Printing all the nodes 
    # with minimum degree 
    print("Nodes with minimum degree : ", 
                                end = "")
     
    for i in range(1, n + 1) :
        if (m[i] == mini) :
            print(i, end = " "); 
 
# Driver code 
if __name__ == "__main__" : 
 
    # Count of nodes and edges 
    n = 4; m = 6; 
 
    # The edge list 
    edges = [[ 1, 2 ], [ 1, 3 ], 
             [ 1, 4 ], [ 2, 3 ], 
             [ 2, 4 ], [ 3, 4 ]]; 
 
    minMax(edges, m, 4); 
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
     
class GFG 
{
     
static int MAX = 2 * 1000 + 10;
static int MOD = (int) (1e9 + 7);
 
// To store the states of the dp
static long [,]dp = new long[MAX, MAX];
 
// Function to return (a + b) % MOD
static long sum(long a, long b)
{
    return ((a % MOD) + (b % MOD)) % MOD;
}
 
// Function to return (a * b) % MOD
static long mul(long a, long b)
{
    return ((a % MOD) * (b % MOD)) % MOD;
}
 
// Function to return the count
// of special sets
static long cntSpecialSet(int n)
{
 
    // Fill the dp[,] array with the answer
    // for the special sets of size 1
    for (int i = 1; i <= n; i++) 
    {
        dp[1, i] = 1;
 
        // Take prefix sum of the current row which
        // will be used to fill the next row
        dp[1, i] += dp[1, i - 1];
    }
 
    // Fill the rest of the dp[,] array
    for (int i = 2; i <= n; i++) 
    {
 
        // Recurrence relation
        for (int j = 2; j <= n; j++) 
        {
            dp[i, j] = dp[i - 1, j - 2];
        }
 
        // Calculate the prefix sum
        for (int j = 1; j <= n; j++) 
        {
            dp[i, j] = sum(dp[i, j], dp[i, j - 1]);
        } 
    }
 
    long ways = 1, ans = 0;
 
    for (int i = 1; i <= n; i++) 
    {
 
        // To find special set of size i
        ways = mul(ways, i);
 
        // Addition of special sets of all sizes
        ans = sum(ans, mul(ways, dp[i, n]));
    }
 
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 3;
 
    Console.WriteLine(cntSpecialSet(n));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
b// JavaScript implementation of the approach
 
 
const MAX = 2 * 1000 + 10;
const MOD = 1e9 + 7;
 
// To store the states of the dp
let dp = new Array(MAX).fill(0).map(()=>new Array(MAX).fill(0));
 
// Function to return (a + b) % MOD
function sum(a, b)
{
    return ((a % MOD) + (b % MOD)) % MOD;
}
 
// Function to return (a * b) % MOD
function mul(a, b)
{
    return ((a % MOD) * (b % MOD)) % MOD;
}
 
// Function to return the count
// of special sets
function cntSpecialSet(n)
{
 
    // Fill the dp[][] array with the answer
    // for the special sets of size 1
    for (let i = 1; i <= n; i++) {
        dp[1][i] = 1;
 
        // Take prefix sum of the current row which
        // will be used to fill the next row
        dp[1][i] += dp[1][i - 1];
    }
 
    // Fill the rest of the dp[][] array
    for (let i = 2; i <= n; i++) {
 
        // Recurrence relation
        for (let j = 2; j <= n; j++) {
            dp[i][j] = dp[i - 1][j - 2];
        }
 
        // Calculate the prefix sum
        for (let j = 1; j <= n; j++) {
            dp[i][j] = sum(dp[i][j], dp[i][j - 1]);
        }
    }
 
    let ways = 1 , ans = 0;
 
    for (let i = 1; i <= n; i++) {
 
        // To find special set of size i
        ways = mul(ways, i);
 
        // Addition of special sets of all sizes
        ans = sum(ans, mul(ways, dp[i][n]));
    }
 
    return ans;
}
 
// Driver code
 
let n = 3;
 
document.write(cntSpecialSet(n),"</br>");
 
/// This code is contributed by shinjanpatra
 
</script>

Output:

Time Complexity: O(n²)

Auxiliary Space: O(MAX²)

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!

Count number of Special Set

C++

Java

Python3

C#

Javascript

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US