Given two integers N and M, where N denotes the count of ‘0’ and M denotes the count of ‘1’, and an integer K, the task is to find the maximum number of binary strings that can be generated of the following two types:
- A string can consist of K ‘0‘s and a single ‘1‘.
- A string can consist of K ‘1‘s and a single ‘0‘.
Examples:
Input: N = 4, M = 4, K = 2
Output: 6
Explanation:
Count of ‘0‘s = 4
Count of ‘1‘s = 4
Possible ways to combine 0’s and 1’s under given constraints are {“001”, “001”} or {“001”, “110”} or {“110”, “110”}
Therefore, at most 2 combinations exists in a selection.
Each combination can be arranged in K + 1 ways, i.e. “001” can be rearranged to form “010, “100” as well.
Therefore, the maximum possible strings that can be generated is 3 * 2 = 6Input: N = 101, M = 231, K = 15
Output: 320
Approach:
Follow the steps below to solve the problem:
- Consider the following three conditions to generate maximum possible combinations of binary strings:
- Number of combinations cannot exceed N.
- Number of combinations cannot exceed M.
- Number of combinations cannot exceed (A+B)/(K + 1).
- Therefore, the maximum possible combinations are min(A, B, (A + B)/ (K + 1)).
- Therefore, the maximum possible strings that can be generated are (K + 1) * min(A, B, (A + B)/ (K + 1)).
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 generate maximum // possible strings that can be generated long long countStrings(long long A, long long B, long long K) { long long X = (A + B) / (K + 1); // Maximum possible strings return (min(A, min(B, X)) * (K + 1)); } int main() { long long N = 101, M = 231, K = 15; cout << countStrings(N, M, K); return 0; } |
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG{ // Function to generate maximum // possible strings that can be generated static long countStrings(long A, long B, long K) { long X = (A + B) / (K + 1); // Maximum possible strings return (Math.min(A, Math.min(B, X)) * (K + 1)); } // Driver Code public static void main (String[] args) { long N = 101, M = 231, K = 15; System.out.print(countStrings(N, M, K)); } } // This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach # Function to generate maximum # possible strings that can be # generated def countStrings(A, B, K): X = (A + B) // (K + 1) # Maximum possible strings return (min(A, min(B, X)) * (K + 1)) # Driver codeN, M, K = 101, 231, 15print(countStrings(N, M, K))# This code is contributed divyeshrabadiya07 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to generate maximum // possible strings that can be generated static long countStrings(long A, long B, long K) { long X = (A + B) / (K + 1); // Maximum possible strings return (Math.Min(A, Math.Min(B, X)) * (K + 1)); } // Driver Code public static void Main (string[] args) { long N = 101, M = 231, K = 15; Console.Write(countStrings(N, M, K)); } } // This code is contributed by rock_cool |
Javascript
<script>// JavaScript Program to implement // the above approach // Function to generate maximum // possible strings that can be generated function countStrings(A, B, K) { let X = Math.floor((A + B) / (K + 1)); // Maximum possible strings return (Math.min(A, Math.min(B, X)) * (K + 1)); } let N = 101, M = 231, K = 15; document.write(countStrings(N, M, K)); // This code is contributed by Surbhi Tyagi.</script> |
Output:
320
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
