La primera solución que nos viene a la mente es la que aprendimos en la escuela. Si la suma de los dígitos de un número es un múltiplo de 3, entonces el número es un múltiplo de 3, por ejemplo, para 612, la suma de los dígitos es 9, por lo que es un múltiplo de 3. Pero esta solución no es eficiente. Debe obtener todos los dígitos decimales uno por uno, sumarlos y luego verificar si la suma es un múltiplo de 3.
Hay un patrón en la representación binaria de un número que se puede usar para encontrar si un número es un múltiplo de 3. Si la diferencia entre el recuento de bits impares establecidos (bits establecidos en posiciones impares) y los bits pares establecidos es un múltiplo de 3 entonces es el número.
Ejemplo: 23 (00..10111)
1) Obtenga la cuenta de todos los bits establecidos en posiciones impares (para 23 es 3).
2) Obtenga la cuenta de todos los bits establecidos en posiciones pares (para 23 es 1).
3) Si la diferencia entre los dos recuentos anteriores es un múltiplo de 3, entonces el número también es un múltiplo de 3.
(Para 23 es 2, entonces 23 no es un múltiplo de 3)
Tome algunos ejemplos más como 21, 15, etc. …
Algorithm: isMutlipleOf3(n)
1) Make n positive if n is negative.
2) If number is 0 then return 1
3) If number is 1 then return 0
4) Initialize: odd_count = 0, even_count = 0
5) Loop while n != 0
a) If rightmost bit is set then increment odd count.
b) Right-shift n by 1 bit
c) If rightmost bit is set then increment even count.
d) Right-shift n by 1 bit
6) return isMutlipleOf3(odd_count - even_count)
Prueba:
Sea la representación binaria del número: abcde.
En forma decimal este número será: 
Cada potencia par de 2 se puede representar como 3n + 1, y cada potencia impar de 2 se puede representar como 3n – 1. Por ejemplo:
ans so on...
Por lo tanto, la forma decimal se convierte en:
[Tex](3n)(a+b+c+d+e) + (a - b + c - d + e) \\[/Tex](multiple of 3)
Para que este número sea divisible por 3, el término 
debe ser divisible por 3.
Por lo tanto, para que el número sea divisible por, la diferencia entre el recuento de bits impares (a + c + e) y los bits pares (b + d) debe ser divisible por 3.
Complejidad de tiempo: O(logn)
Programa:
C++
// CPP program to check if n is a multiple of 3
#include <bits/stdc++.h>
using namespace std;
/* Function to check if n is a multiple of 3*/
int isMultipleOf3(int n)
{
int odd_count = 0;
int even_count = 0;
/* Make no positive if +n is multiple of 3
then is -n. We are doing this to avoid
stack overflow in recursion*/
if (n < 0)
n = -n;
if (n == 0)
return 1;
if (n == 1)
return 0;
while (n) {
/* If odd bit is set then
increment odd counter */
if (n & 1)
odd_count++;
/* If even bit is set then
increment even counter */
if (n & 2)
even_count++;
n = n >> 2;
}
return isMultipleOf3(abs(odd_count - even_count));
}
/* Program to test function isMultipleOf3 */
int main()
{
int num = 24;
if (isMultipleOf3(num))
printf("%d is multiple of 3", num);
else
printf("%d is not a multiple of 3", num);
return 0;
}
Java
// Java program to check if
// n is a multiple of 3
import java.lang.*;
import java.util.*;
class GFG {
// Function to check if n
// is a multiple of 3
static int isMultipleOf3(int n)
{
int odd_count = 0;
int even_count = 0;
/* Make no positive if +n is multiple
of 3 then is -n. We are doing this to
avoid stack overflow in recursion*/
if (n < 0)
n = -n;
if (n == 0)
return 1;
if (n == 1)
return 0;
while (n != 0) {
/* If odd bit is set then
increment odd counter */
if ((n & 1) != 0)
odd_count++;
/* If even bit is set then
increment even counter */
if ((n & 2) != 0)
even_count++;
n = n >> 2;
}
return isMultipleOf3(Math.abs(odd_count - even_count));
}
/* Program to test function isMultipleOf3 */
public static void main(String[] args)
{
int num = 24;
if (isMultipleOf3(num) != 0)
System.out.println(num + " is multiple of 3");
else
System.out.println(num + " is not a multiple of 3");
}
}
// This code is contributed by Sahil_Bansall
Python3
# Python program to check if n is a multiple of 3 # Function to check if n is a multiple of 3 def isMultipleOf3(n): odd_count = 0 even_count = 0 # Make no positive if + n is multiple of 3 # then is -n. We are doing this to avoid # stack overflow in recursion if(n < 0): n = -n if(n == 0): return 1 if(n == 1): return 0 while(n): # If odd bit is set then # increment odd counter if(n & 1): odd_count += 1 # If even bit is set then # increment even counter if(n & 2): even_count += 1 n = n >> 2 return isMultipleOf3(abs(odd_count - even_count)) # Program to test function isMultipleOf3 num = 24 if (isMultipleOf3(num)): print(num, 'is multiple of 3') else: print(num, 'is not a multiple of 3') # This code is contributed by Danish Raza
C#
// C# program to check if
// n is a multiple of 3
using System;
class GFG {
// Function to check if n
// is a multiple of 3
static int isMultipleOf3(int n)
{
int odd_count = 0, even_count = 0;
/* Make no positive if +n is multiple
of 3 then is -n. We are doing this to
avoid stack overflow in recursion*/
if (n < 0)
n = -n;
if (n == 0)
return 1;
if (n == 1)
return 0;
while (n != 0) {
/* If odd bit is set then
increment odd counter */
if ((n & 1) != 0)
odd_count++;
/* If even bit is set then
increment even counter */
if ((n & 2) != 0)
even_count++;
n = n >> 2;
}
return isMultipleOf3(Math.Abs(odd_count - even_count));
}
// Driver Code
public static void Main()
{
int num = 24;
if (isMultipleOf3(num) != 0)
Console.Write(num + " is multiple of 3");
else
Console.Write(num + " is not a multiple of 3");
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to check if n
// is a multiple of 3
// Function to check if n
// is a multiple of 3
function isMultipleOf3( $n)
{
$odd_count = 0;
$even_count = 0;
// Make no positive if +n
// is multiple of 3 then is -n.
// We are doing this to avoid
// stack overflow in recursion
if($n < 0) $n = -$n;
if($n == 0) return 1;
if($n == 1) return 0;
while($n)
{
// If odd bit is set then
// increment odd counter
if($n & 1)
$odd_count++;
// If even bit is set then
// increment even counter
if($n & 2)
$even_count++;
$n = $n >> 2;
}
return isMultipleOf3(abs($odd_count -
$even_count));
}
// Driver Code
$num = 24;
if (isMultipleOf3($num))
echo $num, "is multiple of 3";
else
echo $num, "is not a multiple of 3";
// This code is contributed by vt_m.
?>
Javascript
<script>
/*Function to check if n is a multiple of 3*/
function isMultipleof3(n)
{
odd_count = 0;
even_count = 0;
/* Make no positive if +n is multiple of 3
then is -n. We are doing this to avoid
stack overflowin recursion*/
if(n < 0)
n = -n;
if(n == 0)
return 1;
if(n == 1)
return 0;
while (n)
{
/*If odd bit is set then
increment odd counter*/
if(n & 1)
odd_count++;
/*If even bit is set then
increment even counter*/
if(n & 2)
even_count++;
n = n>>2;
}
return isMultipleof3(Math.abs(odd_count-even_count));
}
/*Program to test function isMultipleof3*/
num = 24;
if(isMultipleof3(num))
document.write(num + " is multiple of 3");
else
document.write(num + " is not a multiple of 3");
// This code is contributed by simranarora5sos
</script>
Producción
24 is multiple of 3
Método eficiente:
Usar programación dinámica (enfoque de arriba hacia abajo usando memorización)
C++
// CPP program to check if n is a multiple of 3
#include <bits/stdc++.h>
using namespace std;
int static dp[1001];
/* Function to check if n is a multiple of 3*/
int isMultipleOf3(int n)
{
int odd_count = 0;
int even_count = 0;
// Base Cases
if (n < 0)
n = -n;
if (n == 0)
return 1;
if (n == 1)
return 0;
// If a value is already present
// in dp, return it
if(dp[n] != -1)
return dp[n];
while (n) {
/* If odd bit is set then
increment odd counter */
if (n & 1)
odd_count++;
/* If even bit is set then
increment even counter */
if (n & 2)
even_count++;
n = n >> 2;
}
dp[n] = isMultipleOf3(abs(odd_count - even_count));
// return dp
return dp[n];
}
/* Program to test function isMultipleOf3 */
int main()
{
int num = 24;
memset(dp, -1, sizeof(dp));
if (isMultipleOf3(num))
printf("%d is multiple of 3", num);
else
printf("%d is not a multiple of 3", num);
return 0;
}
C
// C program to check if n is a multiple of 3
#include <stdio.h>
#include<string.h>
int static dp[1001];
/* Function to check if n is a multiple of 3*/
int isMultipleOf3(int n)
{
int odd_count = 0;
int even_count = 0;
// Base Cases
if (n < 0)
n = -n;
if (n == 0)
return 1;
if (n == 1)
return 0;
// If a value is already present
// in dp, return it
if(dp[n] != -1)
return dp[n];
while (n) {
/* If odd bit is set then
increment odd counter */
if (n & 1)
odd_count++;
/* If even bit is set then
increment even counter */
if (n & 2)
even_count++;
n = n >> 2;
}
int abs = (odd_count - even_count);
if(abs<0)
{
abs= -1*abs;
}
dp[n] = isMultipleOf3(abs);
// return dp
return dp[n];
}
/* Program to test function isMultipleOf3 */
int main()
{
int num = 24;
memset(dp, -1, sizeof(dp));
if (isMultipleOf3(num))
printf("%d is multiple of 3", num);
else
printf("%d is not a multiple of 3", num);
return 0;
}
// This code is contributed by akashish_.
Java
// JAVA program to check if n is a multiple of 3
import java.util.*;
class GFG{
static int []dp ;
/* Function to check if n is a multiple of 3*/
static int isMultipleOf3(int n)
{
int odd_count = 0;
int even_count = 0;
// Base Cases
if (n < 0)
n = -n;
if (n == 0)
return 1;
if (n == 1)
return 0;
// If a value is already present
// in dp, return it
if(dp[n] != -1)
return dp[n];
while (n > 0) {
/* If odd bit is set then
increment odd counter */
if ((n & 1) != 0)
odd_count++;
/* If even bit is set then
increment even counter */
if ((n & 2) != 0)
even_count++;
n = n >> 2;
}
dp[n] = isMultipleOf3(Math.abs(odd_count - even_count));
// return dp
return dp[n];
}
/* Program to test function isMultipleOf3 */
public static void main(String[] args)
{
int num = 24;
dp = new int[1001];
Arrays.fill(dp, -1);
if (isMultipleOf3(num) == 1)
System.out.printf("%d is multiple of 3", num);
else
System.out.printf("%d is not a multiple of 3", num);
}
}
// This codeiscontributed by Rajput-Ji
Python3
# Python program to check if n is a multiple of 3 dp = [-1 for i in range(1001)]; ''' Function to check if n is a multiple of 3 ''' def isMultipleOf3(n): odd_count = 0; even_count = 0; # Base Cases if (n < 0): n = -n; if (n == 0): return 1; if (n == 1): return 0; # If a value is already present # in dp, return it if (dp[n] != -1): return dp[n]; while (n > 0): ''' * If odd bit is set then increment odd counter ''' if ((n & 1) != 0): odd_count+=1; ''' * If even bit is set then increment even counter ''' if ((n & 2) != 0): even_count+=1; n = n >> 2; dp[n] = isMultipleOf3(abs(odd_count - even_count)); # return dp return dp[n]; ''' Program to test function isMultipleOf3 ''' if __name__ == '__main__': num = 24; if (isMultipleOf3(num) == 1): print(num,"is multiple of 3"); else: print(num," is not a multiple of 3"); # This code is contributed by Rajput-Ji
C#
// C# program to check if
// n is a multiple of 3
using System;
class GFG {
static int []dp = new int[1001];
/* Function to check if n is a multiple of 3*/
static int isMultipleOf3(int n)
{
int odd_count = 0;
int even_count = 0;
// Base Cases
if (n < 0)
n = -n;
if (n == 0)
return 1;
if (n == 1)
return 0;
// If a value is already present
// in dp, return it
if(dp[n] != -1)
return dp[n];
while (n > 0) {
/* If odd bit is set then
increment odd counter */
if ((n & 1) != 0)
odd_count++;
/* If even bit is set then
increment even counter */
if ((n & 2) != 0)
even_count++;
n = n >> 2;
}
dp[n] = isMultipleOf3(Math.Abs(odd_count - even_count));
// return dp
return dp[n];
}
// Driver Code
public static void Main()
{
int num = 24;
for(int i = 0; i < 1001; i++) {
dp[i] = -1;
}
if (isMultipleOf3(num) == 1)
Console.Write(num + " is multiple of 3");
else
Console.Write(num + " is not a multiple of 3");
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program to check if n is a multiple of 3
let dp = [];
for(let i = 0; i < 1001; i++) {
dp[i] = -1;
}
/* Function to check if n is a multiple of 3*/
function isMultipleOf3(n)
{
let odd_count = 0;
let even_count = 0;
// Base Cases
if (n < 0)
n = -n;
if (n == 0)
return 1;
if (n == 1)
return 0;
// If a value is already present
// in dp, return it
if(dp[n] != -1)
return dp[n];
while (n) {
/* If odd bit is set then
increment odd counter */
if (n & 1)
odd_count++;
/* If even bit is set then
increment even counter */
if (n & 2)
even_count++;
n = n >> 2;
}
dp[n] = isMultipleOf3(Math.abs(odd_count - even_count));
// return dp
return dp[n];
}
/* Program to test function isMultipleOf3 */
let num = 24;
if (isMultipleOf3(num))
document.write(num + " is multiple of 3");
else
document.write(num + " is not a multiple of 3");
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
24 is multiple of 3
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Método: Comprobar que el número dado es múltiplo de 3 o no usar la división módulo.
C++
// C++ program to check if given number is multiple of 3 or
// not using modulo division
#include <iostream>
using namespace std;
int main()
{
// input number
int num = 24;
cout << num;
// checking if the given number if multiple of 3 or not
// using modulo division operator if the output of num%3
// is equal to 0 then it is considered as multiple of 3
// otherwise not a multiple of 3
if (num % 3 == 0) {
cout << " is multiple of 3";
}
else {
cout << " is not multiple of 3";
}
return 0;
}
// this code is contributed by gangarajula laxmi
C#
// C# program to check if given number is multiple of 3 or
// not using modulo division
using System;
public class GFG {
static public void Main()
{
// input number
int num = 24;
// checking if the given number if multiple of 3 or
// not using modulo division operator if the output
// of num%3 is equal to 0 then it is considered as
// multiple of 3 otherwise not a multiple of 3
if (num % 3 == 0) {
Console.WriteLine(num+" is multiple of 3");
}
else {
Console.WriteLine(num+" is not multiple of 3");
}
}
}
// This code is contributed by laxmigangarajula03
Javascript
<script>
// JavaScript code for the above approach
// input number
let num = 24;
document.write(num);
// checking if the given number if multiple of 3 or not
// using modulo division operator if the output of num%3
// is equal to 0 then it is considered as multiple of 3
// otherwise not a multiple of 3
if (num % 3 == 0) {
document.write(" is multiple of 3");
}
else {
document.write(" is not multiple of 3");
}
// This code is contributed by Potta Lokesh
</script>
Producción
24 is multiple of 3
Artículos relacionados:
Comprobación de la divisibilidad en una
división basada en DFA
de secuencia binaria . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA