The average of the set bit counts in a given binary string after all possible K operations

In this problem, we need to find the average of the set bit count after performing all selected K operations on the given string.

Brute force methods can be used to solve the problem, but we will use probability principles to overcome the time complexity of brute force methods.

Problem Statement - We are given an integer N, an array arr[] containing K positive integers, and a binary string of length N containing only set bits. We need to find the average of the set bit count after performing all possible K operations. In the i-th operation, we can flip any arr[i] bit in the given string.

Example

Input– N = 2, arr[] = {1, 2}

Output– 1

Description – The initial binary string is 11.

• In the first step, we can flip the first character and the string will be 01.

• In the second operation, we need to flip any two bits. So the string will become 10.

• The second selection can start by flipping the second character from the first step and the string will be 10.

• In the second step of the current operation, we need to flip any 2 bits, and the string can be 01.

So, we have two choices, the final string can be 01 or 10.

Total selections = 2, total set bits in final string = 2, ans = 2/2 = 1.

Input– N = 3, arr[] = {2, 2}

Output– 1.6667

Explanation – We have an initial string which is 111.

• In the first operation, we can flip any 2 characters. So the string could be 001, 100, 010.

• In the second operation, we can flip 2 bits in the resulting string from the first operation.

• When we flip any two bits of 001, we get 111, 010 and 100.

• When we flip any 2 digits of 100, we can get 010, 111 and 001.

• When we flip any two bits of 010, we can get 100, 001 and 111.

So, in the last operation, we got a total of 9 different strings.

The total number of setting digits in 9 strings=15, the total number of operations=9, the answer=15/9=1.6667

method one

Here, we will use the principle of probability to solve this problem. Suppose that after performing i-1 operations, the average value of the set bits is p and the average value of the unset bits is q. We need to calculate the average of the set bits and unset bits in the ith operation.

So, the updated value of p can be the average of the new set bits of p - the average of the new closed bits.

algorithm

• Initialize P to N because we initially have N set bits, and initialize Q to 0 because we initially have 0 set bits.

• Traverse the operation array.

• Initialize prev_p and prev_q using P and Q values.

• Update the P value using prev_p - prev_p * arr[i] / N prev_q * arr[i] / N, which will average the inverted bits to the set bits and average the set bits Invert to unset bits

• Update Q value.

• Return P value.

Example

Example

#include <bits/stdc++.h>
using namespace std;

double getAverageBits(int len, int K, int array[]) {
   // to store the average '1's in the binary string
   double P = len;
   // to store the average '0's in the binary string
   double Q = 0;
   // Traverse the array array[]
   for (int i = 0; i < K; i++) {
      // Initialize the prev_p and prev_q with P and Q, which we got from the previous iteration
      double prev_p = P, prev_q = Q;
      // Update the average '1's
      P = prev_p - prev_p * array[i] / len + prev_q * array[i] / len;
      // Update the average '0's
      Q = prev_q - prev_q * array[i] / len + prev_p * array[i] / len;
   }
   return P;
}
int main() {
   int N = 2;
   int array[] = {1};
   int K = sizeof(array) / sizeof(array[0]);
   cout << "The average number of set bits after performing the operations is " << getAverageBits(N, K, array);
   return 0;
}

Output

The average number of set bits after performing the operations is 1

Time complexity - O(K), where K is the length of the array.

Space Complexity - O(1) since we are not using any extra space.

In this tutorial we learned to find the average set bit after performing all possible choices of K operations. In single selection we need to perform all the operations given in the array.

The above is the detailed content of The average of the set bit counts in a given binary string after all possible K operations. For more information, please follow other related articles on the PHP Chinese website!