Dados dos números N y M que denotan el conteo de unos y ceros respectivamente, la tarea es maximizar el conteo de strings binarias de longitud 3, que constan de 0 y 1 en ellas, que se pueden formar a partir de los N 1 y M dados. 0 _
Ejemplos:
Entrada: N = 4, M = 5
Salida: 3
Explicación:
Strings posibles = { “001”, “011”, “001” }
Entrada: N = 818, M = 234
Salida: 234
Enfoque ingenuo: se pueden formar strings binarias de tres longitudes según las siguientes condiciones:
- Si N > M: Si N > 2, entonces reduzca N en 2, M en 1, y dado que se genera una string de tipo 110 , aumente el conteo en 1.
- Si N ≤ M: Si M > 2, entonces reduzca M en 2, N en 1, y dado que se genera una string de tipo 001 , aumente la cuenta en 1.
Por lo tanto, la idea es iterar un ciclo hasta que N o M se conviertan en cero y seguir actualizando el conteo de la string de acuerdo con las condiciones anteriores.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
4
Complejidad de tiempo: O(max(A, B))
Espacio auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, observe que el número total de strings binarias que se pueden formar será un mínimo de N, M y (N + M)/3 como:
- Si N es mínimo y tenemos M ≥ 2*N entonces se puede hacer toda la string de tipo 110 .
- Si M es mínimo y tenemos N ≥ 2*M entonces se puede hacer toda la string de tipo 001 .
- De lo contrario, el recuento total será (N + M)/3 y se pueden formar strings de ambos tipos, 110 y 001 .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
4
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA