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),因为我们在不使用额外空间的情况下更新了给定的字符串。
我们只是基于观察来解决了上述问题。有时候,对不同输入和输出的观察比逻辑和数学运算更重要。