Maximize count of 001 and 110 that can be formed using M 0s and N 1s
Given two integers N(denoting number of â1â) and M(denoting number of â0â). The task is to maximize the number of â001â or â110â patterns that can be formed using the given number of characters.
Examples:
Input: N = 5, M = 5
Output: 3
Explanation: Possible patterns are {001, 110, 001}Input: N = 7, M = 10
Output: 5
Approach: This problem can be solved by dividing the whole problem into cases. Follow the steps below to solve the given problem.
- If N/2 >= M then only 001 patterns will be formed and max number of patterns in such case will be M.
- If M/2 >= N then only 110 patterns will be formed and max number of patterns in such case will be N.
- Else if abs(N-M) < 2*min(N, M) in that case (N+M)/3 will be output.
- Print the result according to the above conditions.
Below is the implementation of the above approach:
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum // possible patterns that can be formed int w3wiki( int N, int M) { // To store the number of patterns // formed by using 0 and 1 int ans = 0; if ((N / 2) >= M) { ans = M; } else if ((M / 2) >= N) { ans = N; } else { ans = (N + M) / 3; } return ans; } // Driver Code int main() { int N, M; N = 7; M = 10; // Function call cout << w3wiki(N, M); return 0; } |
Java
// Java program for the above approach class GFG { // Function to find the maximum // possible patterns that can be formed static int w3wiki( int N, int M) { // To store the number of patterns // formed by using 0 and 1 int ans = 0 ; if ((N / 2 ) >= M) { ans = M; } else if ((M / 2 ) >= N) { ans = N; } else { ans = (N + M) / 3 ; } return ans; } // Driver Code public static void main(String args[]) { int N, M; N = 7 ; M = 10 ; // Function call System.out.println(w3wiki(N, M)); } } // This code is contributed by gfgking |
Python3
# Python 3 code to implement above approach # Function to find the maximum # possible patterns that can be formed def w3wiki(N, M): # To store the number of patterns # formed by using 0 and 1 ans = 0 if ((N / / 2 ) > = M): ans = M elif ((M / / 2 ) > = N): ans = N else : ans = (N + M) / / 3 return ans # Driver Code if __name__ = = "__main__" : N = 7 M = 10 # Function call print (w3wiki(N, M)) # This code is contributed by ukasp. |
C#
// C# program for the above approach using System; class GFG { // Function to find the maximum // possible patterns that can be formed static int w3wiki( int N, int M) { // To store the number of patterns // formed by using 0 and 1 int ans = 0; if ((N / 2) >= M) { ans = M; } else if ((M / 2) >= N) { ans = N; } else { ans = (N + M) / 3; } return ans; } // Driver Code public static void Main() { int N, M; N = 7; M = 10; // Function call Console.Write(w3wiki(N, M)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the maximum // possible patterns that can be formed function w3wiki(N, M) { // To store the number of patterns // formed by using 0 and 1 let ans = 0; if (Math.floor(N / 2) >= M) { ans = M; } else if (Math.floor(M / 2) >= N) { ans = N; } else { ans = Math.floor((N + M) / 3); } return ans; } // Driver Code let N, M; N = 7; M = 10; // Function call document.write(w3wiki(N, M)); // This code is contributed by Potta Lokesh </script> |
Output
5
Time Complexity: O(1)
Auxiliary Space: O(1)