multiple of 3 Algorithm
The multiple of 3 algorithm is a simple and effective method to determine if a given number is a multiple of 3. This algorithm is based on the property of the divisibility rule for 3, which states that a number is divisible by 3 if the sum of its digits is also divisible by 3. The algorithm works by adding up the digits of the number and checking if the resulting sum is divisible by 3. If the sum is divisible by 3, then the original number is also a multiple of 3. Otherwise, the number is not a multiple of 3. This method can be easily implemented in various programming languages and can be used to test numbers of any size.
To use the multiple of 3 algorithm, first, break down the given number into individual digits. Then, sum up the digits and check if the sum is divisible by 3. If necessary, repeat the process for the sum until a single-digit number is obtained. If the final single-digit sum is 3, 6, or 9, then the original number is a multiple of 3. This algorithm is not only applicable to base 10 numbers but also works for numbers in other bases. In essence, the multiple of 3 algorithm provides a quick and efficient way to verify the divisibility of numbers by 3, making it a valuable tool in various mathematical and programming applications.
/**
* Check if a given number is multiple of 3
* Basic way of doing is : if sum of digits of number is multiple of 3,
* number is divisible by 3.
*
* However another efficient way of doing it is:
* Count the number of set bits at even positions.
* Count the number of set bits at odd positions.
* if difference is multiple of 3, number will be multiple of 3.
*
* Proof:
* We can prove it by taking the example of 11 in decimal numbers.
* (It will apply to 3 in binary numbers as well.)
* AB = 10A + B ( A and B are digits of number AB)
* AB = 11A + (B - A)
* Clearly if (B-A) is multiple of 11, number would be muliple of 11.
* We can do it similarly for 3 digits
* ABC = 100A + 10B + C
* = 99A + A + 11B - B + C
* = 11(9A + B) + (A - B + C)
* Clearly if A-B+C is multiple of 11, ABC would be multiple as well.
* similarly for 4 digits
* ABCD = 1000A + 100B + 10C + D
* = (1001A – 999B + 11C) + (D + B – A -C )
* So, if (B + D – A – C) is a multiple of 11 then is ABCD.
*/
#include <iostream>
bool is_multiple_of_3( int n )
{
// change to positive if negative
if ( n < 0 ) {
n = -n;
}
if ( n == 0 ) {
return true;
}
if ( n == 1 ) {
return false;
}
int even_count = 0;
int odd_count = 0;
while ( n ) {
if ( n & 1 ) {
++odd_count;
}
n >>= 1;
if ( n & 1 ) {
++even_count;
}
n >>= 1;
}
return is_multiple_of_3( even_count - odd_count );
}
int main()
{
int num;
std::cout << "Enter a number:";
std::cin >> num;
if (is_multiple_of_3(num)) {
std::cout << num << " is multiple of 3" << std::endl;
} else {
std::cout << num << " is not a multiple of 3" << std::endl;
}
return 0;
}
