C++ 通过翻转字符来修改二进制字符串，使得任何包含1的索引对既不是互质的，也不是彼此可被整除的

在这个问题中，我们给定了一个长度为4*N的二进制字符串，我们需要翻转二进制字符串中的0，使得任何包含’1’的索引对既不是互质的，也不是彼此可被整除的。

在这里，我们可以通过观察来解决这个问题。字符串包含了4*N个字符。我们可以从最后开始翻转N个字符，它们位于偶数索引上。

问题陈述 - 我们给定一个整数N和一个长度为4*N的二进制字符串，初始时所有位都为0。我们需要以这样的方式翻转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}的字符。

方法

在这种方法中，我们将从最后开始翻转N个字符，它们位于偶数位置，以便根据给定条件获得结果字符串。

例如，K = 3，初始二进制字符串为’000000000000’。当我们在最后的偶数索引上翻转3个字符时，字符串变为000000010101，索引值为{8, 10, 12}。如果我们翻转第7个索引处的字符，它与所有其他索引都是互质的。如果我们翻转第6个索引处的字符，12可以被6整除。因此，我们只能从最后开始翻转N个字符，它们位于偶数索引上。

步骤

• 通过4*N初始化’len’变量的值。

• 使用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)，因为我们在不使用额外空间的情况下更新了给定的字符串。

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