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

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 onestop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various productbased companies by providing Online Mock Test Series and many more benefits.
Happy learning!