Dada una string de caracteres binarios, compruebe si es múltiplo de 3 o no.
Ejemplos:
Input : 1 0 1 0 Output : NO Explanation : (1 0 1 0) is 10 and hence not a multiple of 3 Input : 1 1 0 0 Output : YES Explanation : (1 1 0 0) is 12 and hence a multiple of 3
Enfoque 1: un método simple es convertir el número binario en su representación decimal y luego verificar si es un múltiplo de 3 o no. Ahora, cuando se trata de DFA (Deterministic Finite Automata) , no existe el concepto de memoria, es decir, no puede almacenar la string cuando se proporciona, por lo que el método anterior no sería aplicable. En términos simples, un DFA toma una string como entrada y la procesa. Si alcanza el estado final, se acepta, de lo contrario se rechaza. Como no puede almacenar la string, la entrada se toma carácter por carácter.
El DFA para el problema dado es:
Como, cuando un número se divide por 3, solo hay 3 posibilidades. El resto puede ser 0, 1 o 2. Aquí, el estado 0 representa que el resto cuando el número se divide por 3 es 0. El estado 1 representa que el resto cuando el número se divide por 3 es 1 y, de manera similar, el estado 2 representa que el resto cuando el número se divide por 3 es 2. Entonces, si una string llega al estado 0 al final, se acepta, de lo contrario se rechaza.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to illustrate
// DFA for multiple of 3
#include <bits/stdc++.h>
using namespace std;
// checks if binary characters
// are multiple of 3
bool isMultiple3(char c[], int size)
{
// initial state is 0th
char state = '0';
for (int i = 0; i < size; i++) {
// storing binary digit
char digit = c[i];
switch (state) {
// when state is 0
case '0':
if (digit == '1')
state = '1';
break;
// when state is 1
case '1':
if (digit == '0')
state = '2';
else
state = '0';
break;
// when state is 2
case '2':
if (digit == '0')
state = '1';
break;
}
}
// if final state is 0th state
if (state == '0')
return true;
return false;
}
// Driver's Code
int main()
{
// size of binary array
int size = 5;
// array of binary numbers
// Here it is 21 in decimal
char c[] = { '1', '0', '1', '0', '1' };
// if binary numbers are a multiple of 3
if (isMultiple3(c, size))
cout << "YES\n";
else
cout << "NO\n";
return 0;
}
Java
// Java Program to illustrate
// DFA for multiple of 3
import java.io.*;
class GFG
{
// checks if binary characters
// are multiple of 3
static boolean isMultiple3(char c[], int size)
{
// initial state is 0th
char state = '0';
for (int i = 0; i < size; i++) {
// storing binary digit
char digit = c[i];
switch (state) {
// when state is 0
case '0':
if (digit == '1')
state = '1';
break;
// when state is 1
case '1':
if (digit == '0')
state = '2';
else
state = '0';
break;
// when state is 2
case '2':
if (digit == '0')
state = '1';
break;
}
}
// if final state is 0th state
if (state == '0')
return true;
return false;
}
// Driver Code
public static void main (String[] args)
{
// size of binary array
int size = 5;
// array of binary numbers
// Here it is 21 in decimal
char c[] = { '1', '0', '1', '0', '1' };
// if binary numbers are a multiple of 3
if (isMultiple3(c, size))
System.out.println ("YES");
else
System.out.println ("NO");
}
}
// This code is contributed by vt_m
Python3
# Python program to check if the binary String is divisible
# by 3.
# Function to check if the binary String is divisible by 3.
def CheckDivisibilty(A):
oddbits = 0;
evenbits = 0;
for counter in range(len(A)):
# checking if the bit is nonzero
if (A[counter] == '1'):
# checking if the nonzero bit is at even
# position
if (counter % 2 == 0):
evenbits+=1;
else:
oddbits+=1;
# Checking if the difference of non-zero oddbits and
# evenbits is divisible by 3.
if (abs(oddbits - evenbits) % 3 == 0):
print("Yes" + "");
else:
print("No" + "");
# Driver Program
if __name__ == '__main__':
A = "10101";
CheckDivisibilty(A);
# This code contributed by umadevi9616 Added code in Python
C#
// C# Program to illustrate
// DFA for multiple of 3
using System;
class GFG {
// checks if binary characters
// are multiple of 3
static bool isMultiple3(char []c, int size)
{
// initial state is 0th
char state = '0';
for (int i = 0; i < size; i++)
{
// storing binary digit
char digit = c[i];
switch (state)
{
// when state is 0
case '0':
if (digit == '1')
state = '1';
break;
// when state is 1
case '1':
if (digit == '0')
state = '2';
else
state = '0';
break;
// when state is 2
case '2':
if (digit == '0')
state = '1';
break;
}
}
// if final state is 0th state
if (state == '0')
return true;
return false;
}
// Driver Code
public static void Main ()
{
// size of binary array
int size = 5;
// array of binary numbers
// Here it is 21 in decimal
char []c = { '1', '0', '1', '0', '1' };
// if binary numbers are a multiple of 3
if (isMultiple3(c, size))
Console.WriteLine ("YES");
else
Console.WriteLine ("NO");
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Program to illustrate
// DFA for multiple of 3
// checks if binary characters
// are multiple of 3
function isMultiple3($c,$size)
{
// initial state is 0th
$state = '0';
for ($i = 0; $i < $size; $i++)
{
// storing binary digit
$digit = $c[$i];
switch ($state)
{
// when state is 0
case '0':
if ($digit == '1')
$state = '1';
break;
// when state is 1
case '1':
if ($digit == '0')
$state = '2';
else
$state = '0';
break;
// when state is 2
case '2':
if ($digit == '0')
$state = '1';
break;
}
}
// if final state is 0th state
if ($state == '0')
return true;
return false;
}
// Driver Code
// size of binary array
$size = 5;
// array of binary numbers
// Here it is 21 in decimal
$c= array('1', '0', '1', '0', '1');
// if binary numbers are
// a multiple of 3
if (isMultiple3($c, $size))
echo "YES\n";
else
echo "NO\n";
//This code is contributed by mits
?>
Javascript
<script>
// JavaScript Program to illustrate
// DFA for multiple of 3
// checks if binary characters
// are multiple of 3
function isMultiple3(c, size)
{
// initial state is 0th
let state = '0';
for (let i = 0; i < size; i++) {
// storing binary digit
let digit = c[i];
switch (state) {
// when state is 0
case '0':
if (digit == '1')
state = '1';
break;
// when state is 1
case '1':
if (digit == '0')
state = '2';
else
state = '0';
break;
// when state is 2
case '2':
if (digit == '0')
state = '1';
break;
}
}
// if final state is 0th state
if (state == '0')
return true;
return false;
}
// Driver code
// size of binary array
let size = 5;
// array of binary numbers
// Here it is 21 in decimal
let c = [ '1', '0', '1', '0', '1' ];
// if binary numbers are a multiple of 3
if (isMultiple3(c, size))
document.write ("YES");
else
document.write ("NO");
</script>
Producción
YES
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Enfoque 2: comprobaremos si la diferencia entre el número de posiciones de bits impares distintas de cero y las posiciones de bits pares distintas de cero es divisible por 3 o no.
Matemáticamente -> |pares-probabilidades| divisible por 3
Código:
C++
// C++ program to check if the binary string is divisible
// by 3.
#include <bits/stdc++.h>
using namespace std;
// Function to check if the binary string is divisible by 3.
void CheckDivisibilty(string A)
{
int oddbits = 0, evenbits = 0;
for (int counter = 0; counter < A.length(); counter++) {
// checking if the bit is nonzero
if (A[counter] == '1') {
// checking if the nonzero bit is at even
// position
if (counter % 2 == 0) {
evenbits++;
}
else {
oddbits++;
}
}
}
// Checking if the difference of non-zero oddbits and
// evenbits is divisible by 3.
if (abs(oddbits - evenbits) % 3 == 0) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
// Driver Program
int main()
{
string A = "10101";
CheckDivisibilty(A);
return 0;
}
Java
// Java program to check if the binary String is divisible
// by 3.
import java.util.*;
class GFG
{
// Function to check if the binary String is divisible by 3.
static void CheckDivisibilty(String A)
{
int oddbits = 0, evenbits = 0;
for (int counter = 0; counter < A.length(); counter++)
{
// checking if the bit is nonzero
if (A.charAt(counter) == '1')
{
// checking if the nonzero bit is at even
// position
if (counter % 2 == 0) {
evenbits++;
}
else {
oddbits++;
}
}
}
// Checking if the difference of non-zero oddbits and
// evenbits is divisible by 3.
if (Math.abs(oddbits - evenbits) % 3 == 0) {
System.out.print("Yes" +"\n");
}
else {
System.out.print("No" +"\n");
}
}
// Driver Program
public static void main(String[] args)
{
String A = "10101";
CheckDivisibilty(A);
}
}
// This code is contributed by umadevi9616
Python3
# Python program to check if the binary String is divisible
# by 3.
# Function to check if the binary String is divisible by 3.
def CheckDivisibilty(A):
oddbits = 0;
evenbits = 0;
for counter in range(len(A)):
# checking if the bit is nonzero
if (A[counter] == '1'):
# checking if the nonzero bit is at even
# position
if (counter % 2 == 0):
evenbits += 1;
else:
oddbits += 1;
# Checking if the difference of non-zero oddbits and
# evenbits is divisible by 3.
if (abs(oddbits - evenbits) % 3 == 0):
print("Yes" + "");
else:
print("No" + "");
# Driver Program
if __name__ == '__main__':
A = "10101";
CheckDivisibilty(A);
# This code is contributed by umadevi9616.
C#
// C# program to check if the binary String is divisible
// by 3.
using System;
public class GFG
{
// Function to check if the binary String is divisible by 3.
static void CheckDivisibilty(String A)
{
int oddbits = 0, evenbits = 0;
for (int counter = 0; counter < A.Length; counter++)
{
// checking if the bit is nonzero
if (A[counter] == '1')
{
// checking if the nonzero bit is at even
// position
if (counter % 2 == 0) {
evenbits++;
}
else {
oddbits++;
}
}
}
// Checking if the difference of non-zero oddbits and
// evenbits is divisible by 3.
if (Math.Abs(oddbits - evenbits) % 3 == 0) {
Console.Write("Yes" +"\n");
}
else {
Console.Write("No" +"\n");
}
}
// Driver Program
public static void Main(String[] args)
{
String A = "10101";
CheckDivisibilty(A);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program to check if the binary String is divisible
// by 3.
// Function to check if the binary String is divisible by 3.
function CheckDivisibilty( A) {
var oddbits = 0, evenbits = 0;
for (var counter = 0; counter < A.length; counter++) {
// checking if the bit is nonzero
if (A[counter] == '1') {
// checking if the nonzero bit is at even
// position
if (counter % 2 == 0) {
evenbits++;
} else {
oddbits++;
}
}
}
// Checking if the difference of non-zero oddbits and
// evenbits is divisible by 3.
if (Math.abs(oddbits - evenbits) % 3 == 0) {
document.write("Yes" + "\n");
} else {
document.write("No" + "\n");
}
}
// Driver Program
var A = "10101";
CheckDivisibilty(A);
// This code is contributed by umadevi9616
</script>
Producción
Yes
Complejidad temporal: O(n) donde n es el número de bits.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shubham_rana_77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA