Modify a Binary String by flipping characters such that any pair of indices consisting of 1s are neither co-prime nor divisible by each other
Given an integer N and a binary string consisting of 4*N number of 0s initially, the task is to flip the characters such that any two pair of indices of the string consisting of 1s are neither co-prime nor the pair of indices can be divisible by each other.
Note: Consider 1-based indexing.
Examples:
Input: N = 3, S = “000000000000”
Output: 000000010101
Explanation: In the modified string “000000010101”, the indices of 1s are {8, 10, 12}. In the above set of indices, there does not exist any pair of indices that are co-prime and divisible by each other.Input: N = 2, S = “00000000”
Output: 00000101
Approach: The given problem can be solved based on the observation that if the characters are flipped at the positions 4*N, 4*N – 2, 4*N – 4, … up to N terms, then there doesn’t exist any pair of indices that are divisible by each other and having GCD as 1.
Below is the implementation of the above approach:
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
Time Complexity: O(N)
Auxiliary Space: O(1)