给定二进制字符串在执行所有可能的K次操作后,集合位计数的平均值


在这个问题中,我们需要找到在对给定字符串执行所有可能的K次操作后,集合位计数的平均值。

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

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

示例

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

输出– 1

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

  • 在第一步中,我们可以翻转第一个字符,字符串将变为01。

    • 在第二次操作中,我们需要翻转任意两位。因此字符串将变为10。

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

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

因此,我们有2种选择,最终字符串可以是01或10。

总选择= 2,最终字符串中的总集合位= 2,ans = 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,ans = 15/9 = 1.6667

方法1

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

因此,p的更新值可以是p + 新集合位的平均数 - 新关闭位的平均数。

算法

  • 将P初始化为N,因为我们最初有N个集合位,并将Q初始化为0,因为我们最初有0个关闭位。

  • 遍历操作数组。

  • 将prev_p和prev_q初始化为P和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次操作后找到集合位的平均值。在单次选择中,我们需要执行数组中给出的所有操作。

更新于: 2023年8月17日

70 次浏览

开启你的职业生涯

通过完成课程获得认证

开始
广告