Given a set containing N elements. If two subset X and Y picked then find the probability that both of them contains the same number of elements.
Examples:
Input: 4
Output: 35/128
Input: 2
Output: 3/8
Approach:
Let’s choose a subset X that has r number of elements then Y must contain r number of elements. A subset can have minimum 0 elements and maximum N elements.
Total number of subsets of a set contains N number of elements is
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
, Total possible way to choose X and Y simultaneously will be
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
=
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
=
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
.
Let, P = Total possible way to choose X and Y such that both have the same number of elements.
Then P = 
= 
= 
So the required probability will be 
.
Below is the implementation of the above Approach:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;// Returns value of Binomial// Coefficient C(n, k)int binomialCoeff(int n, int k){ int res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res;}// Iterative Function to// calculate (x^y) in O(log y)int power(int x, unsigned int y){ // Initialize result int res = 1; while (y > 0) { // If y is odd, multiply // x with result if (y & 1) res = res * x; // y must be even now // y = y/2 y = y >> 1; // Change x to x^2 x = x * x; } return res;}// Function to find probabilityvoid FindProbability(int n){ // Calculate total possible // ways and favourable ways. int up = binomialCoeff(2 * n, n); int down = power(2, 2 * n); // Divide by gcd such that // they become relatively coprime int g = __gcd(up, down); up /= g, down /= g; cout << up << "/" << down << endl;}// Driver codeint main(){ int N = 8; FindProbability(N); return 0;} |
Java
// Java implementation of // the above approach class GFG{ // Returns value of Binomial // Coefficient C(n, k) static int binomialCoeff(int n, int k) { int res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // Iterative Function to // calculate (x^y) in O(log y) static int power(int x, int y) { // Initialize result int res = 1; while (y > 0) { // If y is odd, multiply // x with result if ((y & 1) == 1) res = res * x; // y must be even now // y = y/2 y = y >> 1; // Change x to x^2 x = x * x; } return res; } // Recursive function to return gcd of a and b static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find probability static void FindProbability(int n) { // Calculate total possible // ways and favourable ways. int up = binomialCoeff(2 * n, n); int down = power(2, 2 * n); // Divide by gcd such that // they become relatively coprime int g = gcd(up, down); up /= g; down /= g; System.out.println(up + "/" + down); } // Driver code public static void main (String[] args) { int N = 8; FindProbability(N); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of # the above approach import math# Returns value of Binomial # Coefficient C(n, k) def binomialCoeff(n, k): res = 1 # Since C(n, k) = C(n, n-k) if (k > n - k): k = n - k # Calculate value of for i in range(0, k): res = res * (n - i) res = res // (i + 1) return res# Iterative Function to # calculate (x^y) in O(log y) def power(x, y): # Initialize result res = 1 while (y > 0): # If y is odd, multiply # x with result if (y & 1): res = res * x # y must be even now # y = y/2 y = y // 2 # Change x to x^2 x = x * x return res # Function to find probability def FindProbability(n): # Calculate total possible # ways and favourable ways. up = binomialCoeff(2 * n, n) down = power(2, 2 * n) # Divide by gcd such that # they become relatively coprime g = math.gcd(up,down) up = up // g down = down // g print(up, "/", down)# Driver code N = 8FindProbability(N)# This code is contributed by Sanjit_Prasad |
C#
// C# implementation of // the above approach using System;using System.Collections.Generic; class GFG{ // Returns value of Binomial // Coefficient C(n, k) static int binomialCoeff(int n, int k) { int res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res; } // Iterative Function to // calculate (x^y) in O(log y) static int power(int x, int y) { // Initialize result int res = 1; while (y > 0) { // If y is odd, multiply // x with result if ((y & 1) == 1) res = res * x; // y must be even now // y = y/2 y = y >> 1; // Change x to x^2 x = x * x; } return res; } // Recursive function to // return gcd of a and b static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find probability static void FindProbability(int n) { // Calculate total possible // ways and favourable ways. int up = binomialCoeff(2 * n, n); int down = power(2, 2 * n); // Divide by gcd such that // they become relatively coprime int g = gcd(up, down); up /= g; down /= g; Console.WriteLine(up + "/" + down); } // Driver code public static void Main (String[] args) { int N = 8; FindProbability(N); } }// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of// the above approach// Returns value of Binomial// Coefficient C(n, k)function binomialCoeff(n, k){ let res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of for (let i = 0; i < k; ++i) { res *= (n - i); res = parseInt(res / (i + 1)); } return res;}// Iterative Function to// calculate (x^y) in O(log y)function power(x, y){ // Initialize result let res = 1; while (y > 0) { // If y is odd, multiply // x with result if (y & 1) res = res * x; // y must be even now // y = y/2 y = y >> 1; // Change x to x^2 x = x * x; } return res;}// Recursive function to// return gcd of a and b function gcd(a, b) { if (b == 0) return a; return gcd(b, a % b); } // Function to find probabilityfunction FindProbability(n){ // Calculate total possible // ways and favourable ways. let up = binomialCoeff(2 * n, n); let down = power(2, 2 * n); // Divide by gcd such that // they become relatively coprime let g = gcd(up, down); up = parseInt(up / g), down = parseInt(down / g); document.write(up + "/" + down + "<br>");}// Driver code let N = 8; FindProbability(N);</script> |
Output:
6435/32768
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!
