在进行所有可能的K次操作后，给定二进制字符串中设置位计数的平均值

在这个问题中，我们需要对给定的字符串进行所有选择的 K 次运算后，求出设置位计数的平均值。

可以使用暴力方法来解决问题，但我们将使用概率原理来克服暴力方法的时间复杂度。

问题陈述 - 我们给定一个整数 N，包含 K 个正整数的数组 arr[]，以及一个长度为 N 的二进制字符串，其中只包含设置位。我们需要找出在执行所有可能的 K 次操作后，设置位计数的平均值。在第 i 次操作中，我们可以翻转给定字符串中的任何 arr[i] 位。

示例

输入– N = 2, arr[] = {1, 2}

输出– 1

说明 – 初始二进制字符串为 11。

• 第一步，我们可以翻转第一个字符，字符串将是01。

• 在第二次操作中，我们需要翻转任意两个位。所以字符串将变为10。

• 第二个选择可以从翻转第一步中的第二个字符开始，字符串将为 10。

• 在当前操作的第二步中，我们需要翻转任意2个位，字符串可以是01。

所以，我们有两个选择，最终的字符串可以是01或者10。

总选择 = 2，最终字符串中的总设置位 = 2，ans = 2/2 = 1。

输入– N = 3, arr[] = {2, 2}

输出– 1.6667

Explanation – 我们有一个初始字符串是111。

• 在第一个操作中，我们可以翻转任意 2 个字符。因此，字符串可以是 001、100、010。

• 在第二个操作中，我们可以翻转第一个操作得到的结果字符串中的2个位。

  

  Live PPT

  一款AI智能化生成演示内容的在线工具。只需输入一句话、粘贴一段内容、或者导入文件，AI生成高质量PPT。

  下载

• 当我们翻转001的任意两个位时，我们得到111、010和100。

• 当我们翻转 100 的任意 2 位时，我们可以得到 010、111 和 001。

• 当我们翻转010的任意两个位时，我们可以得到100、001和111。

所以，在上一次操作中，我们得到了总共9个不同的字符串。

9个字符串中的总设置位数=15，总操作次数=9，答案=15/9=1.6667

方法一

在这里，我们将使用概率原理来解决这个问题。假设在执行了 i-1 次操作后，设置位的平均值为 p，非设置位的平均值为 q。我们需要计算第 i 次操作中设置位和非设置位的平均值。

所以，p的更新值可以是p + 新设置位的平均数 - 新关闭位的平均数。

算法

• 将P初始化为N，因为我们最初有N个设置位，将Q初始化为0，因为我们最初有0个设置位。

• 遍历操作数组。

• 使用 P 和 Q 值初始化 prev_p 和 prev_q。

• 使用prev_p - prev_p * arr[i] / N + prev_q * arr[i] / N更新P值，这将平均将反转的位添加到设置的位中，并将平均设置的位反转为未设置的位

• 更新 Q 值。

• 返回 P 值。

Example

示例

#include 
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;
}

输出

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

时间复杂度 - O(K)，其中K是数组的长度。

空间复杂度 - O(1)，因为我们没有使用任何额外的空间。

在本教程中，我们学习了在执行 K 操作的所有可能选择后找到平均设置位。在单选中，我们需要执行数组中给出的所有操作。