Dado un número entero N y una string binaria que consta de 4*N número de 0 inicialmente, la tarea es invertir los caracteres de modo que dos pares cualesquiera de índices de la string que consta de 1 no sean coprimos ni el par de índices pueda ser divisibles entre sí.
Nota: considere la indexación basada en 1 .
Ejemplos:
Entrada: N = 3, S = “ 000000000000”
Salida: 000000010101
Explicación: En la string modificada “000000010101”, los índices de 1 son {8, 10, 12}. En el conjunto de índices anterior, no existe ningún par de índices que sean coprimos y divisibles entre sí.Entrada: N = 2, S = “00000000”
Salida: 00000101
Enfoque: El problema dado se puede resolver basándose en la observación de que si los caracteres se invierten en las posiciones 4*N, 4*N – 2, 4*N – 4, … hasta N términos , entonces no existe ningún par de índices que son divisibles entre sí y tienen MCD igual a 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
#include <iostream> using namespace std; // Function to modify a string such // that there doesn't exist any pair // of indices consisting of 1s, whose // GCD is 1 and are divisible by each other void findString(char S[], int N) { int strLen = 4 * N; // Flips characters at indices // 4N, 4N - 2, 4N - 4 .... upto N terms for (int i = 1; i <= N; i++) { S[strLen - 1] = '1'; strLen -= 2; } // Print the string for (int i = 0; i < 4 * N; i++) { cout << S[i]; } } // Driver code int main() { int N = 2; char S[4 * N]; // Initialize the string S for (int i = 0; i < 4 * N; i++) S[i] = '0'; // function call findString(S, N); return 0; } // This code is contributed by aditya7409.
Java
// Java program for the above approach import java.io.*; class GFG { // Function to modify a string such // that there doesn't exist any pair // of indices consisting of 1s, whose // GCD is 1 and are divisible by each other public static void findString(char S[], int N) { int strLen = 4 * N; // Flips characters at indices // 4N, 4N - 2, 4N - 4 .... upto N terms for (int i = 1; i <= N; i++) { S[strLen - 1] = '1'; strLen -= 2; } // Print the string System.out.println(S); } // Driver Code public static void main(String[] args) { int N = 2; char S[] = new char[4 * N]; // Initialize the string S for (int i = 0; i < 4 * N; i++) S[i] = '0'; findString(S, N); } }
Python3
# Python3 program for the above approach # Function to modify a string such # that there doesn't exist any pair # of indices consisting of 1s, whose # GCD is 1 and are divisible by each other def findString(S, N) : strLen = 4 * N # Flips characters at indices # 4N, 4N - 2, 4N - 4 .... upto N terms for i in range(1, N + 1): S[strLen - 1] = '1' strLen -= 2 # Print the string for i in range(4 * N): print(S[i], end = "") # Driver code N = 2 S = [0] * (4 * N) # Initialize the string S for i in range(4 * N): S[i] = '0' # function call findString(S, N) # This code is contributed by sanjoy_62.
C#
// C# program to implement // the above approach using System; public class GFG { // Function to modify a string such // that there doesn't exist any pair // of indices consisting of 1s, whose // GCD is 1 and are divisible by each other public static void findString(char[] S, int N) { int strLen = 4 * N; // Flips characters at indices // 4N, 4N - 2, 4N - 4 .... upto N terms for (int i = 1; i <= N; i++) { S[strLen - 1] = '1'; strLen -= 2; } // Print the string Console.WriteLine(S); } // Driver Code public static void Main(String[] args) { int N = 2; char[] S = new char[4 * N]; // Initialize the string S for (int i = 0; i < 4 * N; i++) S[i] = '0'; findString(S, N); } } // This code is contributed by souravghosh0416.
Javascript
<script> // Function to modify a string such // that there doesn't exist any pair // of indices consisting of 1s, whose // GCD is 1 and are divisible by each other function findString(S, N) { var strLen = 4 * N; // Flips characters at indices // 4N, 4N - 2, 4N - 4 .... upto N terms for (var i = 1; i <= N; i++) { S[strLen - 1] = "1"; strLen -= 2; } // Print the string for (var i = 0; i < 4 * N; i++) { document.write(S[i]); } } // Driver code var N = 2; var S = [...Array(4 * N)]; // Initialize the string S for (var i = 0; i < 4 * N; i++) S[i] = "0"; // function call findString(S, N); // This code is contributed by rdtank. </script>
00000101
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aditya7409 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA