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

在这个问题中，我们需要找到在给定字符串上执行K次操作后设定位数的平均值。

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

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

示例

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

输出 - 1

解释 - 初始二进制字符串是11。

• 第一次操作中，我们可以翻转第一个字符，字符串将变为01。
  • 第二次操作中，我们需要翻转任意两个位。所以字符串将变为10。
• 第二次选择可以从第一次操作中翻转第二个字符，字符串将变为10。
  • 当前操作的第二次操作中，我们需要翻转任意两个位，字符串可以变为01。

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

总选择数=2，最终字符串中的总设定位数=2，答案=2/2=1。

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

输出 - 1.6667

解释 - 初始字符串为111。

• 在第一次操作中，我们可以翻转任意2个字符。所以字符串可以是001、100、010。
• 在第二次操作中，我们可以翻转从第一次操作得到的结果字符串中的2个位。
  • 当我们翻转001的任意2个位时，我们得到111、010和100。
  • 当我们翻转100的任意2个位时，我们可以得到010、111和001。
  • 当我们翻转010的任意2个位时，我们可以得到100、001和111。

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

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

方法

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

因此，更新后的p值可以是p + 新设置位的平均数 – 新未设置位的平均数。

步骤

• 将P初始化为N，因为最初有N个已设置位，并将Q初始化为0，因为最初没有已设置位。

• 遍历操作的数组。

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

• 用prev_p – prev_p * arr[i] / N + prev_q * arr[i] / N更新P值，这将将平均未设置的位翻转成设置位，并将平均设置的位翻转成未设置位。

• 更新Q值。

• 返回P值。

示例

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

输出

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

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

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

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