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

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

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

Camera课程

Python教程

Java教程

Web教程

数据库教程

图形图像教程

办公软件教程

Linux教程

计算机教程

大数据教程

开发工具教程