Given an integer, N. Consider the set of first N natural numbers A = {1, 2, 3, …, N}. Let M and P be two non-empty subsets of A. The task is to count the number of unordered pairs of (M, P) such that M and P are disjoint sets. Note that the order of M and P doesn’t matter. Examples:
Input: N = 3
Output: 6
Explanation: The unordered pairs are ({1}, {2}), ({1}, {3}), ({2}, {3}), ({1}, {2, 3}), ({2}, {1, 3}), ({3}, {1, 2}).Input: N = 2
Output: 1Input: N = 10
Output: 28501
Approach:
- Lets assume there are only 6 elements in the set {1, 2, 3, 4, 5, 6}.
- When you count the number of subsets with 1 as one of the element of first subset, it comes out to be 211.
- Counting number of subsets with 2 being one of the element of first subset, it comes out to be 65, because 1’s not included as order of sets doesn’t matter.
- Counting number of subset with 3 being one of the element of first set it comes out to be 65, here a pattern can be observed.
- Pattern:
5 = 3 * 1 + 2 19 = 3 * 5 + 4 65 = 3 * 19 + 8 211 = 3 * 65 + 16 S(n) = 3 * S(n-1) + 2(n – 2)
- Expanding it until n->2 (means numbers of elements n-2+1=n-1) 2(n-2) * 3(0) + 2(n – 3) * 31 + 2(n – 4) * 32 + 2(n – 5) * 33 + … + 2(0) * 3(n – 2) From Geometric progression, a + a * r0 + a * r1 + … + a * r(n – 1) = a * (rn – 1) / (r – 1)
- S(n) = 3(n – 1) – 2(n – 1). Remember S(n) is number of subsets with 1 as a one of the elements of first subset but to get the required result, Denoted by T(n) = S(1) + S(2) + S(3) + … +S(n)
- It also forms a Geometric progression, so we calculate it by formula of sum of GP T(n) = (3n – 2n + 1 + 1)/2
- As we require T(n) % p where p = 109 + 7 We have to use Fermat’s little theorem a-1 = a(m – 2) (mod m) for modular division
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define p 1000000007// Modulo exponentiation functionlong long power(long long x, long long y){ // Function to calculate (x^y)%p in O(log(y)) long long res = 1; x = x % p; while (y > 0) { if (y & 1) res = (res * x) % p; y = y >> 1; x = (x * x) % p; } return res % p;}// Driver functionint main(){ long long n = 3; // Evaluating ((3^n-2^(n+1)+1)/2)%p long long x = (power(3, n) % p + 1) % p; x = (x - power(2, n + 1) + p) % p; // From Fermats’s little theorem // a^-1 ? a^(m-2) (mod m) x = (x * power(2, p - 2)) % p; cout << x << "\n";} |
Java
// Java implementation of the approachclass GFG{static int p = 1000000007;// Modulo exponentiation functionstatic long power(long x, long y){ // Function to calculate (x^y)%p in O(log(y)) long res = 1; x = x % p; while (y > 0) { if (y % 2 == 1) res = (res * x) % p; y = y >> 1; x = (x * x) % p; } return res % p;}// Driver Codepublic static void main(String[] args){ long n = 3; // Evaluating ((3^n-2^(n+1)+1)/2)%p long x = (power(3, n) % p + 1) % p; x = (x - power(2, n + 1) + p) % p; // From Fermats's little theorem // a^-1 ? a^(m-2) (mod m) x = (x * power(2, p - 2)) % p; System.out.println(x);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approachp = 1000000007# Modulo exponentiation functiondef power(x, y): # Function to calculate (x^y)%p in O(log(y)) res = 1 x = x % p while (y > 0): if (y & 1): res = (res * x) % p; y = y >> 1 x = (x * x) % p return res % p# Driver Coden = 3# Evaluating ((3^n-2^(n+1)+1)/2)%px = (power(3, n) % p + 1) % px = (x - power(2, n + 1) + p) % p# From Fermats’s little theorem# a^-1 ? a^(m-2) (mod m)x = (x * power(2, p - 2)) % pprint(x)# This code is contributed by Mohit Kumar |
C#
// C# implementation of the approachusing System;class GFG{static int p = 1000000007;// Modulo exponentiation functionstatic long power(long x, long y){ // Function to calculate (x^y)%p in O(log(y)) long res = 1; x = x % p; while (y > 0) { if (y % 2 == 1) res = (res * x) % p; y = y >> 1; x = (x * x) % p; } return res % p;}// Driver Codestatic public void Main (){ long n = 3; // Evaluating ((3^n-2^(n+1)+1)/2)%p long x = (power(3, n) % p + 1) % p; x = (x - power(2, n + 1) + p) % p; // From Fermats's little theorem // a^-1 ? a^(m-2) (mod m) x = (x * power(2, p - 2)) % p; Console.Write(x);}}// This code is contributed by ajit. |
Javascript
// JS implementation of the approachlet p = 1000000007n// Modulo exponentiation functionfunction power(x, y){ // Function to calculate (x^y)%p in O(log(y)) let res = 1n; x = x % p; while (y > 0n) { if (y & 1n) res = (res * x) % p; y = y >> 1n; x = (x * x) % p; } return res % p;}// Driver functionlet n = 3n;// Evaluating ((3^n-2^(n+1)+1)/2)%plet x = (power(3n, n) % p + 1n) % p;x = (x - power(2n, n + 1n) + p) % p;// From Fermats’s little theorem// a^-1 ? a^(m-2) (mod m)x = (x * power(2n, p - 2n)) % p;console.log(x)// This code is contributed by phasing17 |
Time Complexity: O(log(n)+log(p))
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!
