Generate a Binary String without any consecutive 0’s and at most K consecutive 1’s

0 0 6 minutes read

Given two integers N and M, the task is to construct a binary string with the following conditions :

The Binary String consists of N 0’s and M 1’s
The Binary String has at most K consecutive 1’s.
The Binary String does not contain any adjacent 0’s.

If it is not possible to construct such a binary string, then print -1.

Examples:

Input: N = 5, M = 9, K = 2
Output: 01101101101101
Explanation:
The string “01101101101101” satisfies the following conditions:

No consecutive 0’s are present.

No more than K(= 2) consecutive 1’s are present.

Input: N = 4, M = 18, K = 4
Output: 1101111011110111101111

Approach:

To construct a binary string satisfying the given properties, observe the following:

For no two ‘0‘s to be consecutive, there should be at least a ‘1‘ placed between them.
Therefore, for N number of ‘0‘s, there should be at least N-1 ‘1‘s present for a string of required type to be generated.
Since no more than K consecutive ‘1‘s can be placed together, for N 0’s, there can be a maximum (N+1) * K ‘1‘s possible.
Therefore, the number of ‘1‘s should lie within the range:

N – 1 ? M ? (N + 1) * K

If the given values N and M do not satisfy the above condition, then print -1.
Otherwise, follow the steps below to solve the problem:
- Append ‘0‘s to the final string.
- Insert ‘1‘ in between each pair of ‘0′s. Subtract N – 1 from M, as N – 1 ‘1‘s have already been placed.
- For the remaining ‘1‘s, place min(K – 1, M) ‘1‘s alongside each already placed ‘1‘s, to ensure that no more than K ‘1’s are placed together.
- For any remaining ‘1‘s, append them to the beginning and end of the final string.
Finally, print the string generated.

Below is the implementation of the above approach:

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to construct the binary string
string ConstructBinaryString(int N, int M,
                             int K)
{
    // Conditions when string construction
    // is not possible
    if (M < (N - 1) || M > K * (N + 1))
        return "-1";
 
    string ans = "";
 
    // Stores maximum 1's that
    // can be placed in between
    int l = min(K, M / (N - 1));
    int temp = N;
    while (temp--) {
        // Place 0's
        ans += '0';
 
        if (temp == 0)
            break;
 
        // Place 1's in between
        for (int i = 0; i < l; i++) {
            ans += '1';
        }
    }
 
    // Count remaining M's
    M -= (N - 1) * l;
 
    if (M == 0)
        return ans;
 
    l = min(M, K);
    // Place 1's at the end
    for (int i = 0; i < l; i++)
        ans += '1';
 
    M -= l;
    // Place 1's at the beginning
    while (M > 0) {
        ans = '1' + ans;
        M--;
    }
 
    // Return the final string
    return ans;
}
 
// Driver Code
int main()
{
    int N = 5, M = 9, K = 2;
 
    cout << ConstructBinaryString(N, M, K);
}

Java

// Java implementation of 
// the above approach 
import java.io.*;
class GFG{
     
// Function to construct the binary string
static String ConstructBinaryString(int N, int M,
                                    int K)
{
     
    // Conditions when string construction
    // is not possible
    if (M < (N - 1) || M > K * (N + 1))
        return "-1";
 
    String ans = "";
 
    // Stores maximum 1's that
    // can be placed in between
    int l = Math.min(K, M / (N - 1));
    int temp = N;
     
    while (temp != 0)
    {
        temp--;
         
        // Place 0's
        ans += '0';
 
        if (temp == 0)
            break;
 
        // Place 1's in between
        for(int i = 0; i < l; i++) 
        {
            ans += '1';
        }
    }
 
    // Count remaining M's
    M -= (N - 1) * l;
 
    if (M == 0)
        return ans;
 
    l = Math.min(M, K);
     
    // Place 1's at the end
    for(int i = 0; i < l; i++)
        ans += '1';
 
    M -= l;
     
    // Place 1's at the beginning
    while (M > 0) 
    {
        ans = '1' + ans;
        M--;
    }
 
    // Return the final string
    return ans;
}
 
// Driver code    
public static void main(String[] args)
{
    int N = 5, M = 9, K = 2;
     
    System.out.println(ConstructBinaryString(N, M, K));
}
}
 
// This code is contributed by rutvik_56

Python3

# Python3 implementation of
# the above approach
 
# Function to construct the binary string
def ConstructBinaryString(N, M, K):
 
    # Conditions when string construction
    # is not possible
    if(M < (N - 1) or M > K * (N + 1)):
        return '-1'
 
    ans = ""
 
    # Stores maximum 1's that
    # can be placed in between
    l = min(K, M // (N - 1))
    temp = N
     
    while(temp):
        temp -= 1
 
        # Place 0's
        ans += '0'
 
        if(temp == 0):
            break
 
        # Place 1's in between
        for i in range(l):
            ans += '1'
 
    # Count remaining M's
    M -= (N - 1) * l
 
    if(M == 0):
        return ans
 
    l = min(M, K)
     
    # Place 1's at the end
    for i in range(l):
        ans += '1'
 
    M -= l
     
    # Place 1's at the beginning
    while(M > 0):
        ans = '1' + ans
        M -= 1
 
    # Return the final string
    return ans
 
# Driver Code 
if __name__ == '__main__':
 
    N = 5
    M = 9
    K = 2
     
    print(ConstructBinaryString(N, M , K))
 
# This code is contributed by Shivam Singh

C#

// C# implementation of 
// the above approach 
using System;
class GFG{
      
// Function to construct the binary string
static String ConstructBinaryString(int N, int M,
                                    int K)
{
      
    // Conditions when string construction
    // is not possible
    if (M < (N - 1) || M > K * (N + 1))
        return "-1";
  
    string ans = "";
  
    // Stores maximum 1's that
    // can be placed in between
    int l = Math.Min(K, M / (N - 1));
    int temp = N;
      
    while (temp != 0)
    {
        temp--;
          
        // Place 0's
        ans += '0';
  
        if (temp == 0)
            break;
  
        // Place 1's in between
        for(int i = 0; i < l; i++) 
        {
            ans += '1';
        }
    }
  
    // Count remaining M's
    M -= (N - 1) * l;
  
    if (M == 0)
        return ans;
  
    l = Math.Min(M, K);
      
    // Place 1's at the end
    for(int i = 0; i < l; i++)
        ans += '1';
  
    M -= l;
      
    // Place 1's at the beginning
    while (M > 0) 
    {
        ans = '1' + ans;
        M--;
    }
  
    // Return the final string
    return ans;
}
  
// Driver code    
public static void Main(string[] args)
{
    int N = 5, M = 9, K = 2;
      
    Console.Write(ConstructBinaryString(N, M, K));
}
}
  
// This code is contributed by Ritik Bansal

Javascript

<script>
// JavaScript program for the above approach
 
// Function to construct the binary string
function ConstructBinaryString(N, M, K)
{
      
    // Conditions when string construction
    // is not possible
    if (M < (N - 1) || M > K * (N + 1))
        return "-1";
  
    let ans = "";
  
    // Stores maximum 1's that
    // can be placed in between
    let l = Math.min(K, M / (N - 1));
    let temp = N;
      
    while (temp != 0)
    {
        temp--;
          
        // Place 0's
        ans += '0';
  
        if (temp == 0)
            break;
  
        // Place 1's in between
        for(let i = 0; i < l; i++)
        {
            ans += '1';
        }
    }
  
    // Count remaining M's
    M -= (N - 1) * l;
  
    if (M == 0)
        return ans;
  
    l = Math.min(M, K);
      
    // Place 1's at the end
    for(let i = 0; i < l; i++)
        ans += '1';
  
    M -= l;
      
    // Place 1's at the beginning
    while (M > 0)
    {
        ans = '1' + ans;
        M--;
    }
  
    // Return the final string
    return ans;
}
 
// Driver Code    
     
        let N = 5, M = 9, K = 2;
      
    document.write(ConstructBinaryString(N, M, K));
                     
</script>

Output:

01101101101101

Time Complexity: O(N+M)
Auxiliary Space: O(N+M)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!