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>
Producción
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>
Producción
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)