修改一個二進位制字串，透過翻轉字元使包含 1 的任何一對索引既非互質數也不是彼此可整除

---

在這個問題中，提供了一個長度為 4*N 的二進位制字串，我們需要翻轉二進位制字串的零，以便由“1”組成的索引對既不能互質也不能彼此可整除。

這裡，我們可以透過觀察來解決問題。該字串包含 4*N 個字元。我們可以翻轉最後面 N 個位於偶數索引處的字元。

問題陳述 – 給定一個整數 N 和一個長度為 4*N 的二進位制字串，該字串最初包含所有零。我們需要以這樣的方式將“0”翻轉為“1”，使由“1”組成的索引對在結果字串中彼此不能整除且互質。另外，給定索引從 1 開始。

注意 – 互質數是沒有共同因子（除了 1）的數。

示例

輸入 – str = ‘000000000000’ K = 3

輸出 – ‘000000010101’

解釋 – 我們翻轉了 {8, 10, 12} 索引處的字元，因為任何一對都不彼此可整除。此外，任何一對都不是互質數，因為它們都有 2 作為共同因子。

輸入 – str = ‘00000000’ K = 2

輸出 – ‘00000101’

解釋– 我們將 {6, 8} 索引處的字元翻轉，因為它們不能彼此整除，也不是互素數。

輸入– str = ‘0000’ K = 1

輸出– ‘0001’

解釋– 我們將 {4} 索引處的字元翻轉。

方法 1

在此方法中，我們將翻轉最後 N 個位於偶數位置的字元，以便根據給定條件獲得結果字串。

例如，K = 3，初始二進位制字串將為‘000000000000’。當我們從最後翻轉偶數索引處的 3 個字元時，字串將變為 000000010101，索引值分別為 {8, 10, 12}。如果我們翻轉第 7 索引處的字元，則 7 和所有其他字元互素。如果我們翻轉第 6 索引處的字元，則 12 能被 6 整除。因此，我們只能翻轉最後 N 個位於偶數索引處的字元。

演算法

• 將‘len’變數的值初始化為 4*N。

• 使用 for 迴圈執行 N 次迭代。

• 翻轉 len -1 索引處的字元，因為字串索引從 0 開始。

• 將‘len’的值減 2，因為我們只需要翻轉偶數索引處的字元。

• 最後，返回更新後的字串。

示例

#include <iostream>
using namespace std;
// function to modify the string str by flipping 0 to 1 at particular indices so that any 2 indices are not co-prime of each other and divisible by each other
string getstring(char str[], int N) {
   int len = 4 * N;
   // flip total N 0's to 1's at 4N, 4N-2, 4N-4, 4N-6, ... indices
   for (int i = 1; i <= N; i++) {
      str[len - 1] = '1';
      len -= 2;
   }
   return str;
}
int main() {
   int N = 4;
   char str[N * 4];
   // Initialize the string str
   for (int i = 0; i < 4 * N; i++)
      str[i] = '0';
   cout << "The string after modifying is " << getstring(str, N);
   return 0;
}

輸出

The string after modifying is 0000000001010101�SK-�

時間複雜度 – O(N)，因為我們執行了 N 次迭代。

空間複雜度 – O(1)，因為我們在沒有使用額外空間的情況下更新了給定的字串。

我們只是基於觀察解決了上述問題。有時，觀察不同的輸入和輸出比使用數學運算的邏輯更重要。