Tuesday, 26 Oct 2021

# Count all unique outcomes possible by performing S flips on N coins

Given two positive integers N and S, the task is to count the number of unique outcomes possible when S flip operations are performed on N coins.
Examples:

Input: N = 3, S = 4Output: 3Explanation: Considering the intiial configuration of coins to be “HHH”, then the possible combinations of 4 flips are:
Flipping the 1st and 2nd coins once and the third coin twice modifies the configuration to “TTH”.
Flipping the 1st and 3rd coins once and the 2nd coin twice modifies the configuration to “THT”.
Flipping the 2nd and 3rd coins once and the 1st coin twice modifies the configuration to “HTT”.
The above three combinations are unique. Therefore, the total count is 3.
Input: N = 3, S = 6Output: 4

Naive Approach: The given problem can be solved by using recursion whose recursive state is defined as:
Consider F(N, S) represents the number of unique outcomes when N coins are tossed with the total number of flips equals to S.
Then F(N, S) can also be expressed as the sum of all combinations with 1 flip or 2 flips i.e.,

F(N, S) = F(N – 1, S – 1) + F(N – 1, S – 2)

The base case for this recurrence relation is F(K, K) whose value is 1 for all (K > 1).
Below is the table that shows the distribution of F(N, S) = F(N – 1, S – 1) + F(N – 1, S – 2), where F(K, K) = 1.

Follow the below steps to solve the problem:
Declare a function, say numberOfUniqueOutcomes(N, S) that takes the number of coins and flips allowed as the parameters respectively and perform the following steps:
If the value of S is less than N, then return 0 from the function.
If the value of N is S or 1, then return 1 from the function as this is one of the unique combinations.
Recursively return summation of the two recursive states as:

return numberOfUniqueOutcomes(N – 1, S – 1) + numberOfUniqueOutcomes(N – 1, S – 2)

After completing the above steps, print the value returned by the function numberOfUniqueOutcomes(N, S) as the resultant number of outcomes.
Below is the implementation of the above approach:

C++

#include
using namespace std;

int numberOfUniqueOutcomes(int N, int S)
{

if (S < N)         return 0;     if (N == 1 || N == S)         return 1;          return (numberOfUniqueOutcomes(N - 1, S - 1)             + numberOfUniqueOutcomes(N - 1, S - 2)); } int main() {     int N = 3, S = 4;     cout