Maximize count of strings of length 3 that can be formed from N 1s and M 0s
Given two numbers N and M which denotes the count of ones and zeros respectively, the task is to maximize the count of binary strings of length 3, consisting of both 0 and 1 in them, that can be formed from the given N 1s and M 0s.
Examples:
Input: N = 4, M = 5
Output: 3
Explanation:
Possible strings = { â001â, â011â, â001â }
Input: N = 818, M = 234
Output: 234
Naive Approach: Binary strings of three lengths can be formed as per the below conditions:
- If N > M: If N > 2, then reduce N by 2, M by 1, and since a string of type 110 is generated, thus increase the count by 1.
- If N ? M: If M > 2, then reduce M by 2, N by 1, and since a string of type 001 is generated, thus increase the count by 1.
Therefore, the idea is to iterate a loop until N or M becomes zero and keep updating the count of the string according to the above conditions.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that counts the number of // strings of length three that can be // made with given m 0s and n 1s void number_of_strings( int N, int M) { int ans = 0; // Iterate until N & M are positive while (N > 0 && M > 0) { // Case 1: if (N > M) { if (N >= 2) { N -= 2; --M; ++ans; } else { break ; } } // Case 2: else { if (M >= 2) { M -= 2; --N; ++ans; } else { break ; } } } // Print the count of strings cout << ans; } // Driver Code int main() { // Given count of 1s and 0s int N = 4, M = 19; // Function Call number_of_strings(N, M); return 0; } |
Java
// Java program for the above approach import java.util.*; import java.lang.*; class GFG{ // Function that counts the number of // strings of length three that can be // made with given m 0s and n 1s static void number_of_strings( int N, int M) { int ans = 0 ; // Iterate until N & M are positive while (N > 0 && M > 0 ) { // Case 1: if (N > M) { if (N >= 2 ) { N -= 2 ; --M; ++ans; } else { break ; } } // Case 2: else { if (M >= 2 ) { M -= 2 ; --N; ++ans; } else { break ; } } } // Print the count of strings System.out.println(ans); } // Driver Code public static void main (String[] args) { // Given count of 1s and 0s int N = 4 , M = 19 ; // Function call number_of_strings(N, M); } } // This code is contributed by jana_sayantan |
Python3
# Python3 program for the above approach # Function that counts the number of # strings of length three that can be # made with given m 0s and n 1s def number_of_strings(N, M): ans = 0 # Iterate until N & M are positive while (N > 0 and M > 0 ): # Case 1: if (N > M): if (N > = 2 ): N - = 2 M - = 1 ans + = 1 else : break # Case 2: else : if M > = 2 : M - = 2 N - = 1 ans + = 1 else : break # Print the count of strings print (ans) # Driver code if __name__ = = '__main__' : # Given count of 1s and 0s N = 4 M = 19 # Function call number_of_strings(N, M) # This code is contributed by jana_sayantan |
C#
// C# program for the above approach using System; class GFG{ // Function that counts the number of // strings of length three that can be // made with given m 0s and n 1s static void number_of_strings( int N, int M) { int ans = 0; // Iterate until N & M are positive while (N > 0 && M > 0) { // Case 1: if (N > M) { if (N >= 2) { N -= 2; --M; ++ans; } else { break ; } } // Case 2: else { if (M >= 2) { M -= 2; --N; ++ans; } else { break ; } } } // Print the count of strings Console.WriteLine(ans); } // Driver Code public static void Main (String[] args) { // Given count of 1s and 0s int N = 4, M = 19; // Function call number_of_strings(N, M); } } // This code is contributed by jana_sayantan |
Javascript
<script> // javascript program for the above approach // Function that counts the number of // strings of length three that can be // made with given m 0s and n 1s function number_of_strings(N , M) { var ans = 0; // Iterate until N & M are positive while (N > 0 && M > 0) { // Case 1: if (N > M) { if (N >= 2) { N -= 2; --M; ++ans; } else { break ; } } // Case 2: else { if (M >= 2) { M -= 2; --N; ++ans; } else { break ; } } } // Print the count of strings document.write(ans); } // Driver Code // Given count of 1s and 0s var N = 4, M = 19; // Function call number_of_strings(N, M); // This code is contributed by Amit Katiyar </script> |
4
Time Complexity: O(max(A, B))
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, observe that the total number of binary strings that can be formed will be a minimum of N, M, and (N + M)/3 as:
- If N is minimum, and we have M ? 2*N then all the string of type 110 can be made.
- If M is minimum, and we have N ? 2*M then all the string of type 001 can be made.
- Else the total count will be (N + M)/3 and strings of both types 110 and 001 can be made.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that counts the number of // strings of length 3 that can be // made with given m 0s and n 1s void number_of_strings( int N, int M) { // Print the count of strings cout << min(N, min(M, (N + M) / 3)); } // Driver Code int main() { // Given count of 1s and 0s int N = 4, M = 19; // Function Call number_of_strings(N, M); return 0; } |
Java
// Java program for // the above approach class GFG{ // Function that counts the number of // Strings of length 3 that can be // made with given m 0s and n 1s static void number_of_Strings( int N, int M) { // Print the count of Strings System.out.print(Math.min(N, Math.min(M, (N + M) / 3 ))); } // Driver Code public static void main(String[] args) { // Given count of 1s and 0s int N = 4 , M = 19 ; // Function Call number_of_Strings(N, M); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach # Function that counts the number of # strings of length 3 that can be # made with given m 0s and n 1s def number_of_strings(N, M): # Print the count of strings print ( min (N, min (M, (N + M) / / 3 ))) # Driver Code if __name__ = = '__main__' : # Given count of 1s and 0s N = 4 M = 19 # Function call number_of_strings(N, M) # This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approach using System; class GFG{ // Function that counts the number of // Strings of length 3 that can be // made with given m 0s and n 1s static void number_of_Strings( int N, int M) { // Print the count of Strings Console.Write(Math.Min(N, Math.Min(M, (N + M) / 3))); } // Driver Code public static void Main(String[] args) { // Given count of 1s and 0s int N = 4, M = 19; // Function Call number_of_Strings(N, M); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // javascript program for // the above approach// Function that counts the number of // Strings of length 3 that can be // made with given m 0s and n 1s function number_of_Strings(N , M) { // print the count of Strings document.write(Math.min(N, Math.min(M, (N + M) / 3))); } // Driver Code // Given count of 1s and 0s var N = 4, M = 19; // Function Call number_of_Strings(N, M); // This code is contributed by Amit Katiyar </script> |
4
Time Complexity: O(1)
Auxiliary Space: O(1)