Average Value of Set Bit Count in Given Binary String after Performing All Possible Choices of M Operations

Sample Test Cases

Input:   
3
2
2 3
Output: 2
Explanation: 
                        111
                   /     |     \         a[0] = 2, flip exactly 2 bits
                  /      |      \  
                001     100     001
                 |       |       |       a[0] = 3, flip all the bits
                 |       |       |
                110     011     110

The above figure shows all the possible strings that can be generated from the given string.
As shown, three strings, 110, 011, and 110, can be generated in which there are a total of 6 set bits. So, the average number of set bits is 6/3 = 2.

Approach

To solve this problem, we will use the basic principle of probability. Let P(i) and Q(i) be the average number of ones and zeros, respectively, after the ith operation.

It can be observed that the average number of ones after the ith operation, P(i) = average number of ones before the ith operation + the average number of unset bits flipped to set bits - the average number of set bit flipped to unset bits.

The probability of choosing a bit from the N bits is the same for all the bits. So in ith operation, the average number of unset bits flipped to set sits is Q(i - 1) * A[i]/N, where Q(i - 1) is the average number of the unset bit after (i - i)th operation. Similarly, the average number of set bits flipped to unset bits is P(i - 1) * A[i]/N.

So, the formula we got is -

P(i) = P(i - 1) + Q(i - 1) * A[i]/N - P(i - 1) * A[i]/N

Similarly,

Q(i) = Q(i - 1) + P(i - 1) * A[i]/N - Q(i - 1) * A[i]/N

Steps to Solve :

• Declare two variables, P and Q. P and Q store the average number of ones and zeros, respectively, after ith step. Initially, the number of ones is N, and the number of zeros is 0, so initialize P with N and Q with 0.
• Start iterating from i = 0 to i = M - 1.
• Declare the two temporary variables, new_P and new_Q. 
• Calculate the average value of ones and zero after the ith operation using the values of P and Q and store it in new_P and new_Q, respectively.
• Now assign the values of new_P and new_Q to P and Q, respectively.

Code

#include <bits/stdc++.h>
using namespace std;
int main()
{  
   //size of binary string and given array
   int N, M;
   cin >> N >> M;
   //given array
   int a[M] = {};
   for(int i = 0; i < M; ++i){
       cin >> a[i];
   }
   //Initially, the number of ones is N, and the number of zeros is 0, so initialize P with N and Q with 0. 
   long double P = N, Q = 0;
   for(int i = 0; i < M; ++i){
       //compute the value of P[i] and Q[i] using P[i - 1] and Q[i - 1]
       long double new_P = P + Q * a[i]/N - P * a[i]/N;
       long double new_Q = Q - Q * a[i]/N + P * a[i]/N;
       //assign the new values of of P and Q
       P = new_P;
       Q = new_Q; 
   }
   //print answer up to 9 decimal places
   cout << setprecision(9) << P << "\n";
   return 0;
}

Input

3 
2
2 3

Output

2    

Complexity 

Time Complexity

The time complexity is O(M)

Space Complexity

The space complexity is O(1)

Read about Bitwise Operators in C here.

FAQs

1. Why are we using long double instead of double or float?
   We are using long double for better accuracy.

Key Takeaways

In this article, we solved a problem using the basic concept of probability. 

Having a good grasp of probability theory will help you solve advanced problems in the live contest and also help you a lot in aptitude rounds. Check out this content on coding ninjas to better understand it.
Check out this problem - Longest String Chain

To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning!