Find the Good String

Problem Statement

Given an Integer N and and String S of length 4N containing all 0's.

The task is to fill the String S with N number of 1's in such a way

• For any two pair of 1's  inserted in the string,the GCD  of the  position of  that two 1's inserted ≠ 1.
• For any two position  where 1's will be inserted ,they should not be divisible by each other.

Print any Binary String which satisfies above 2 conditions

Examples:

Input:N=3,

S=000000000000  

Output: 000101000100  

Explanation:In the above string we have to insert N number of 1's which in this case is 3 1's are inserted in the position(1 based indexing) 4,6,10. For any two pair of (4,6,10),any two number's GCD ≠ 1 and no two number between (4,6,10) divides each other. So this is an Valid output. 

Input:N=2,S=00000000  

Output: 00010100

Approach:The question can be solved using observation that the pattern 4n,4n-2,4n-4.... upto N terms will always satisfy the Above two conditions.

Solution

Below is the Java implementation of the above approach:

Code

import java.io.*;

class Solution {
    public static void findString(char arr[], int n)
    {
        int strLen = 4 * n;
        // filling N 1's in string in pattern
        // 4N,4N-2,4N-4....upto N terms
        for (int i = 1; i <= n; i++) {
            arr[strLen - 1] = '1';
            strLen -= 2;
        }
        // printing the string
        System.out.println(arr);
    }
   // Driver Code
    public static void main(String[] args)
    {
        int n = 3;
        char arr[] = new char[4 * n];
        Arrays.fill(arr, '0');
        // function call
        findString(arr, n);
    }
}

 Output:

000000010101

Time Complexity: O(n)

Auxiliary Space: O(1)

 Feel free to comment for any improvement and suggestion in comments section

 

For more Data structure and algorithms,computer science,programming,coding related problems search my website.


Learn how to prepare for Information Technology Based companies here