Given an integer N, the task is to count the number of subsets formed from an array of integers from 1 to N which doesn’t contain adjacent elements. A subset can’t be chosen if it satisfies the non-adjacent element condition, but it is possible to add more elements.
Examples:
Input: N = 4
Output: 3
Explanation:
Array is {1, 2, 3, 4}
So to satisfy the condition, the subsets formed are :
{1, 3}, {2, 4}, {1, 4}
Input: N = 5
Output: 4
Approach:
This problem can be solved by using Dynamic Programming. For the last element, we have two choices, either we include it, or we exclude it. Let DP[i] be the number of our desirable subsets ending at index i.
So next Subproblem becomes DP[i-3]
So the DP relation becomes :
DP[i] = DP[i-2] + DP[i-3]
But, we need to observe the base cases:
- When N=0, we cannot form any subset with 0 numbers.
- When N=1, we can form 1 subset, {1}
- When N=2, we can form 2 subsets, {1}, {2}
- When N=3, we can form 2 subsets, {1, 3}, {2}
Below is the implementation of above approach:
C++
// C++ Code to count subsets not containing// adjacent elements from 1 to N#include <bits/stdc++.h>using namespace std;// Function to count subsetsint countSubsets(int N){ if(N <= 2) return N; if(N == 3) return 2; int DP[N + 1] = {0}; DP[0] = 0, DP[1] = 1, DP[2] = 2, DP[3] = 2; for (int i = 4; i <= N; i++) { DP[i] = DP[i - 2] + DP[i - 3]; } return DP[N];}// Driver Codeint main(){ int N = 20; cout << countSubsets(N); return 0;} |
Java
// Java code to count subsets not containing// adjacent elements from 1 to Nclass GFG{// Function to count subsetsstatic int countSubsets(int N){ if(N <= 2) return N; if(N == 3) return 2; int []DP = new int[N + 1]; DP[0] = 0; DP[1] = 1; DP[2] = 2; DP[3] = 2; for(int i = 4; i <= N; i++) { DP[i] = DP[i - 2] + DP[i - 3]; } return DP[N];}// Driver codepublic static void main(String[] args){ int N = 20; System.out.print(countSubsets(N));}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 Code to count subsets # not containing adjacent elements# from 1 to N# Function to count subsetsdef countSubsets(N): if(N <= 2): return N if(N == 3): return 2 DP = [0] * (N + 1) DP[0] = 0 DP[1] = 1 DP[2] = 2 DP[3] = 2 for i in range(4, N + 1): DP[i] = DP[i - 2] + DP[i - 3] return DP[N]# Driver Codeif __name__ == '__main__': N = 20 print(countSubsets(N)) # This code is contributed by Mohit Kumar |
C#
// C# code to count subsets not containing// adjacent elements from 1 to Nusing System;class GFG{// Function to count subsetsstatic int countSubsets(int N){ if(N <= 2) return N; if(N == 3) return 2; int []DP = new int[N + 1]; DP[0] = 0; DP[1] = 1; DP[2] = 2; DP[3] = 2; for(int i = 4; i <= N; i++) { DP[i] = DP[i - 2] + DP[i - 3]; } return DP[N];}// Driver codepublic static void Main(String[] args){ int N = 20; Console.Write(countSubsets(N));}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// javascript code to count subsets not containing// adjacent elements from 1 to N // Function to count subsets function countSubsets(N) { if (N <= 2) return N; if (N == 3) return 2; var DP = Array(N + 1).fill(0); DP[0] = 0; DP[1] = 1; DP[2] = 2; DP[3] = 2; for (i = 4; i <= N; i++) { DP[i] = DP[i - 2] + DP[i - 3]; } return DP[N]; } // Driver code var N = 20; document.write(countSubsets(N));// This code contributed by gauravrajput1</script> |
Output:
265
Time Complexity: O(N)
Space Complexity: O(N)
Efficient approach: Space-optimized approach
In this approach, we optimize the space by using variables.
Implementation steps :
- Initialize variables to store previous computations : prev1, prev2 , prev3, prev4
- The current computation is depend upon the prev3 and prev2.
- After every iteration update these variables to iterate further.
- At last return answer stored in curr.
Implementation:
C++
// C++ Code to count subsets not containing// adjacent elements from 1 to N#include <bits/stdc++.h>using namespace std;// Function to count subsetsint countSubsets(int N){ // Base Case if(N <= 2) return N; if(N == 3) return 2; int prev1 = 0, prev2 = 1, prev3 = 2, prev4 = 2 , curr; for (int i = 4; i <= N; i++) { curr = prev3 + prev2; // assigning value to iterate further prev1 = prev2; prev2= prev3; prev3 = prev4; prev4 = curr; } // return answer return curr;}// Driver Codeint main(){ int N = 20; // function call cout << countSubsets(N); return 0;} |
Java
// Java program for above approachimport java.util.*;public class Main { // Function to count subsets public static int countSubsets(int N) { // Base Case if (N <= 2) { return N; } if (N == 3) { return 2; } int prev1 = 0, prev2 = 1, prev3 = 2; int prev4 = 2, curr = 0; // loop to get the current value // from previous computations for (int i = 4; i <= N; i++) { curr = prev3 + prev2; // assigning value to iterate further prev1 = prev2; prev2 = prev3; prev3 = prev4; prev4 = curr; } // return answer return curr; } // Driver Code public static void main(String[] args) { int N = 20; System.out.println(countSubsets(N)); }} |
Python3
# Python3 Code to count subsets not containing# adjacent elements from 1 to N# Function to count subsetsdef countSubsets(N): # Base Case if(N <= 2): return N if(N == 3): return 2 prev1 = 0 prev2 = 1 prev3 = 2 prev4 = 2 curr = 0 for i in range(4, N+1): curr = prev3 + prev2 # assigning value to iterate further prev1 = prev2 prev2 = prev3 prev3 = prev4 prev4 = curr # return answer return curr# Driver CodeN = 20# function callprint(countSubsets(N)) |
C#
// C# program for above approachusing System;class MainClass { // Function to count subsets public static int CountSubsets(int N) { // Base Case if (N <= 2) { return N; } if (N == 3) { return 2; } int prev1 = 0, prev2 = 1, prev3 = 2, prev4 = 2, curr = 0; // loop to get the current value from previous // computations for (int i = 4; i <= N; i++) { curr = prev3 + prev2; // assigning value to iterate further prev1 = prev2; prev2 = prev3; prev3 = prev4; prev4 = curr; } // return answer return curr; } // Driver Code public static void Main(string[] args) { int N = 20; // function call Console.WriteLine(CountSubsets(N)); }} |
Javascript
// Function to count subsetsfunction countSubsets(N) { // Base Case if (N <= 2) { return N; } if (N == 3) { return 2; } let prev1 = 0, prev2 = 1, prev3 = 2, prev4 = 2 , curr; for (let i = 4; i <= N; i++) { curr = prev3 + prev2; // assigning value to iterate further prev1 = prev2; prev2= prev3; prev3 = prev4; prev4 = curr; } // return answer return curr;}// Driver Codeconst N = 20;// function callconsole.log(countSubsets(N)); |
Output
265
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
