給定二進位制字串在執行所有可能的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次操作後找到集合位的平均值。在單次選擇中，我們需要執行陣列中給出的所有操作。