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




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. 


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.


Below is the Java implementation of the above approach:



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
   // 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);



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

Post a Comment