Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem Statement
2.
Constraints
3.
Sample Test Cases
4.
Approach
5.
Code
5.1.
Input
5.2.
Output
6.
Complexity 
6.1.
Time Complexity
6.2.
Space Complexity
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

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

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Problem Statement

You have an array A[] of size M and a binary string of length N. You have to perform theoperation. In the ith operation, you can flip any arr[i] bits out of N bits. Your task is to find the average value of set bits after performing all the possible choices of M operation. 

Constraints

1 <= N <= 300000
1 <= M <= 300000
1 <= A[i] <= N
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 Qand 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!

 

Previous article
Finding the number of triangles amongst horizontal and vertical line segments
Next article
Find two Integers whose GCD is A, and the Difference Between their Squares is B
Live masterclass