修改一个二进制字符串，通过翻转字符使包含 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)，因为我们在没有使用额外空间的情况下更新了给定的字符串。

我们只是基于观察解决了上述问题。有时，观察不同的输入和输出比使用数学运算的逻辑更重要。