Dada una string binaria S de longitud N , que consta de 0 y 1. La tarea es contar el número de tripletes (i, j, k) tales que S[i] & S[j] = S[j] & S[k] , donde 0 ≤ i < j < k < N y & denota operador AND bit a bit.
Ejemplos:
Entrada: N = 4, S = “0010”
Salida: 4
Explicación: Los siguientes son 4 tripletes que satisfacen la condición S[i] & S[j] = S[j] & S[k]
(0, 1, 2) porque 0 & 0 = 0 & 1,
(0, 1, 3) porque 0 & 0 = 0 & 0,
(0, 2, 3) porque 0 & 1 = 1 & 0,
(1, 2, 3) porque 0 & 1 = 1 & 0.Entrada: N = 5, S = “00101”
Salida: 8
Explicación: 8 tripletes que satisfacen la condición anterior son:
(0, 1, 2) porque 0 & 0 = 0 & 1.
(0, 1, 3) porque 0 & 0 = 0 & 0.
(0, 1, 4) porque 0 & 0 = 0 & 1.
(0, 2, 3) porque 0 & 1 = 1 & 0.
(1, 2, 3) porque 0 & 1 = 1 y 0.
(0, 3, 4) porque 0 y 0 = 0 y 1.
(1, 3, 4) porque 0 y 0 = 0 y 1.
(2, 3, 4) porque 1 y 0 = 0 y 1.
Enfoque ingenuo: la forma más fácil de resolver el problema es:
Genere todos los tripletes posibles y verifique si S[i] & S[j] = S[j] & S[k].
Siga los pasos a continuación para resolver este problema:
- Declare e inicialice una respuesta variable a 0 para almacenar el recuento total.
- Ahora, se necesitan tres bucles anidados para iterar sobre todos los tripletes.
- El primer ciclo itera sobre el índice i , el segundo sobre el índice j comenzando desde i+1 y el tercero sobre el índice k comenzando desde j+1 .
- Ahora, verifique que la condición S[i] & S[j] = S[j] & S[k] sea verdadera o no. Si es verdadero, el incremento de ans en 1 .
- Devuelve el recuento total de trillizos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to count total number of triplets int countTriplets(int n, string& s) { // Stores the count of triplets. int ans = 0; // Iterate over all the triplets. for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { // Extract integer from 'S[i]', // 'S[j]', 'S[k]'. int x = s[i] - '0'; int y = s[j] - '0', z = s[k] - '0'; // If condition 'S[i]' & 'S[j]' // == 'S[j]' &'S[k]' is true, // increment 'ans'. if ((x & y) == (y & z)) { ans++; } } } } // Return the answer return ans; } // Driver code int main() { int N = 4; string S = "0010"; // Function call cout << countTriplets(N, S); return 0; }
Java
// JAVA program for above approach import java.util.*; class GFG { // Function to count total number of triplets public static int countTriplets(int n, String s) { // Stores the count of triplets. int ans = 0; // Iterate over all the triplets. for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { // Extract integer from 'S[i]', // 'S[j]', 'S[k]'. int x = s.charAt(i); int y = s.charAt(j), z = s.charAt(k); // If condition 'S[i]' & 'S[j]' // == 'S[j]' &'S[k]' is true, // increment 'ans'. if ((x & y) == (y & z)) { ans++; } } } } // Return the answer return ans; } // Driver code public static void main(String[] args) { int N = 4; String S = "0010"; // Function call System.out.print(countTriplets(N, S)); } } // This code is contributed by Taranpreet
Python3
# Python3 program for above approach # Function to count total number of triplets def countTriplets(n, s): # Stores the count of triplets. ans = 0 # Iterate over all the triplets. for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): # Extract integer from 'S[i]', S[j], S[k] x = ord(S[i]) - ord("0") y = ord(S[j]) - ord("0") z = ord(S[k]) - ord("0") # If condition 'S[i]' & 'S[j]' # == S[j]' & 'S[k]' # is true, increment ans if (x & y) == (y & z): ans += 1 # return the answer return ans # Driver code N = 4 S = "0010" # function call print(countTriplets(N, S)) # This code is contributed by hrithikgarg03188.
C#
// C# program for above approach using System; public class GFG{ // Function to count total number of triplets static int countTriplets(int n, string s) { // Stores the count of triplets. int ans = 0; // Iterate over all the triplets. for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { // Extract integer from 'S[i]', // 'S[j]', 'S[k]'. int x = s[i]; int y = s[j], z = s[k]; // If condition 'S[i]' & 'S[j]' // == 'S[j]' &'S[k]' is true, // increment 'ans'. if ((x & y) == (y & z)) { ans++; } } } } // Return the answer return ans; } // Driver code static public void Main () { int N = 4; string S = "0010"; // Function call Console.Write(countTriplets(N, S)); } } // This code is contributed by hrithikgarg03188.
Javascript
<script> // JavaScript program for above approach // Function to count total number of triplets const countTriplets = (n, s) => { // Stores the count of triplets. let ans = 0; // Iterate over all the triplets. for (let i = 0; i < n; ++i) { for (let j = i + 1; j < n; ++j) { for (let k = j + 1; k < n; ++k) { // Extract integer from 'S[i]', // 'S[j]', 'S[k]'. let x = s.charCodeAt(i) - '0'.charCodeAt(0); let y = s.charCodeAt(j) - '0'.charCodeAt(0), z = s.charCodeAt(k) - '0'.charCodeAt(0); // If condition 'S[i]' & 'S[j]' // == 'S[j]' &'S[k]' is true, // increment 'ans'. if ((x & y) == (y & z)) { ans++; } } } } // Return the answer return ans; } // Driver code let N = 4; let S = "0010"; // Function call document.write(countTriplets(N, S)); // This code is contributed by rakeshsahni </script>
4
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: La idea de resolver el problema de manera eficiente se basa en las siguientes observaciones:
Observaciones:
- Como S[i] ∈ {0, 1}, solo puede haber 8 posibles tripletes distintos. Analicemos cuántos de estos realmente satisfacen la condición S[i] & S[j] == S[j] & S[k].
Si] S[j] S[k] S[i]&S[j]==S[j]&S[k] 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1
- Después de analizar la tabla de verdad, observe que siempre que S[j] == ‘0’ , la condición siempre se cumple. Además, cuando S[j] == ‘1’ , tanto S[i] como S[k] deberían ser iguales.
- Por lo tanto, itere sobre todos los valores de S[j] y, según el valor de S[j] , simplemente cuente el número de tripletes.
- Si S[j] == ‘0’ , entonces S[i] y S[k] pueden ser cualquier cosa, por lo que el total de formas posibles de elegir cualquier i y k es j * (N – j – 1) .
- De lo contrario, si S[j] == ‘1’ , entonces S[i] y S[k] deberían ser iguales. Entonces, solo los 0 pueden formar pares con 0 y los 1 con 1. Digamos que había x1 0 en el prefijo y x2 0 en el sufijo y y1 y y2 1 en el prefijo y el sufijo. Entonces el total de pares posibles es x1*x2 + y1*y2
Siga los pasos a continuación para resolver este problema:
- Declare una variable (por ejemplo, ans ) para almacenar el conteo de trillizos e inicialícelo en 0.
- Cree una array de prefijos pre y una array de sufijos suf . Estas dos arrays almacenan el número de ceros en el prefijo y el sufijo de la array.
- Para construir una array de prefijos, itere de 0 a N – 1 :
- Si S[i] == ‘0’, entonces pre[i] = pre[i – 1] + 1.
- Si S[i]== ‘1’, entonces pre[i] = pre[i – 1].
- Para construir una array de sufijos, itere de N – 1 a 0 :
- Si S[i] == ‘0’, entonces suf[i] = suf[i + 1] + 1.
- Si S[i] == ‘1’, entonces suf[i] = suf[i + 1].
- Ahora itera de nuevo, de 1 a N – 2 (estamos iterando para S[j]):
- Si S[j] == ‘0’, entonces agregue j * (N – j – 1) a la variable ans según la observación.
- Si S[j] == ‘1’, entonces agregue ‘pre[j – 1]’ * ‘suf[j + 1]’ + (j – ‘pre[j – 1]’) * (N – j – 1 – ‘suf[j + 1]’) a ans según la observación anterior.
- Ahora devuelva la variable ans ya que contiene el recuento final de trillizos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to count number of triplets int countTriplets(int n, string& s) { // Stores the count of triplets. int ans = 0; // 'pre[i]', 'suf[i]', stores the // number of zeroes in // the prefix and suffix vector<int> pre(n), suf(n); // Build the prefix array for (int i = 0; i < n; ++i) { pre[i] = (i == 0 ? 0 : pre[i - 1]) + (s[i] == '0'); } // Build the suffix array. for (int i = n - 1; i >= 0; --i) { suf[i] = (i == n - 1 ? 0 : suf[i + 1]) + (s[i] == '0'); } // Iterate over the middle index // of the triplet. for (int j = 1; j < n - 1; ++j) { // If 'S[j]' == '0' if (s[j] == '0') { ans += j * (n - j - 1); } else { // If 'S[j]' == '1' ans += pre[j - 1] * suf[j + 1] + (j - pre[j - 1]) * (n - j - 1 - suf[j + 1]); } } // Return the answer. return ans; } // Driver code int main() { int N = 4; string S = "0010"; // Function call cout << countTriplets(N, S); return 0; }
Java
// Java program for above approach public class GFG { // Function to count number of triplets static int countTriplets(int n, String s) { // Stores the count of triplets. int ans = 0; // 'pre[i]', 'suf[i]', stores the // number of zeroes in // the prefix and suffix int[] pre = new int[n]; int[] suf = new int[n]; // Build the prefix array for (int i = 0; i < n; ++i) { pre[i] = (i == 0 ? 0 : pre[i - 1]) + ('1' - s.charAt(i)); } // Build the suffix array. for (int i = n - 1; i >= 0; --i) { suf[i] = (i == n - 1 ? 0 : suf[i + 1]) + ('1' - s.charAt(i)); } // Iterate over the middle index // of the triplet. for (int j = 1; j < n - 1; ++j) { // If 'S[j]' == '0' if (s.charAt(j) == '0') { ans += j * (n - j - 1); } else { // If 'S[j]' == '1' ans += pre[j - 1] * suf[j + 1] + (j - pre[j - 1]) * (n - j - 1 - suf[j + 1]); } } // Return the answer. return ans; } // Driver Code public static void main(String[] args) { int N = 4; String S = "0010"; // Function call System.out.println(countTriplets(N, S)); } } // This code is contributed by phasing17
Python3
# Python3 program for above approach # Function to count total number of triplets def countTriplets(n, s): # Stores the count of triplets. ans = 0 # 'pre[i]', 'suf[i]', stores the # number of zeroes in # the prefix and suffix pre = [0]*n suf = [0]*n # Build the prefix array for i in range(0,n): pre[i] = (0 if i == 0 else pre[i - 1]) + (s[i] == '0') # Build the suffix array for i in range(n-1,-1,-1): suf[i] = (0 if i == n - 1 else suf[i + 1]) + (s[i] == '0') # Iterate over the middle index # of the triplet. for j in range(1,n): # If 'S[j]' == '0' if (s[j] == '0'): ans += j * (n - j - 1) else : # If 'S[j]' == '1' ans = ans+ pre[j - 1] * suf[j + 1] + (j - pre[j - 1]) * (n - j - 1 - suf[j + 1]) # Return the answer. return ans # Driver code N = 4 S = "0010" # function call print(countTriplets(N, S)) # This code is contributed by Pushpesh Raj
C#
// C# code to implement the above approach using System; class GFG { // Function to count number of triplets static int countTriplets(int n, string s) { // Stores the count of triplets. int ans = 0; // 'pre[i]', 'suf[i]', stores the // number of zeroes in // the prefix and suffix int[] pre = new int[n]; int[] suf = new int[n]; // Build the prefix array for (int i = 0; i < n; ++i) { pre[i] = (i == 0 ? 0 : pre[i - 1]) + ('1' - s[i]); } // Build the suffix array. for (int i = n - 1; i >= 0; --i) { suf[i] = (i == n - 1 ? 0 : suf[i + 1]) + ('1' - s[i]); } // Iterate over the middle index // of the triplet. for (int j = 1; j < n - 1; ++j) { // If 'S[j]' == '0' if (s[j] == '0') { ans += j * (n - j - 1); } else { // If 'S[j]' == '1' ans += pre[j - 1] * suf[j + 1] + (j - pre[j - 1]) * (n - j - 1 - suf[j + 1]); } } // Return the answer. return ans; } // Driver code public static void Main() { int N = 4; string S = "0010"; // Function call Console.Write(countTriplets(N, S)); } } // This code is contributed by sanjoy_62.
Javascript
<script> // JavaScript code for the above approach function countTriplets(n, s) { // Stores the count of triplets. let ans = 0; // 'pre[i]', 'suf[i]', stores the // number of zeroes in // the prefix and suffix let pre = new Array(n); let suf = new Array(n); // Build the prefix array for (let i = 0; i < n; ++i) { pre[i] = (i == 0 ? 0 : pre[i - 1]) + ('1' - s[i]); } // Build the suffix array. for (let i = n - 1; i >= 0; --i) { suf[i] = (i == n - 1 ? 0 : suf[i + 1]) + ('1' - s[i]); } // Iterate over the middle index // of the triplet. for (let j = 1; j < n - 1; ++j) { // If 'S[j]' == '0' if (s[j] == '0') { ans += j * (n - j - 1); } else { // If 'S[j]' == '1' ans += pre[j - 1] * suf[j + 1] + (j - pre[j - 1]) * (n - j - 1 - suf[j + 1]); } } // Return the answer. return ans; } // Driver Code let N = 4; let S = "0010"; // Function call document.write(countTriplets(N, S)); // This code is contributed by sanjoy_62. </script>
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)