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 stringstring 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 Codeint 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 stringstatic 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 stringdef 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 stringstatic 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 stringfunction 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
