We are given a number and we want to check if the number is Multiple of 3 or not. The very simple first solution comes in our mind is old school way. We can check if a number is multiple of 3 or not by adding all the digits of number. If the total sum of digits is multiple of 3 then the number is also multiple of 3 otherwise it is not. This is simplest way of doing it. We can be more efficient at doing this.
Efficient approach
They idea here is to look into the binary repersentation of the given number. In binary representation of the number, If difference between count of odd set bits (Bitsets at odd positions) and even set bits is multiple of 3 then the number is also multiple of 3.
Algorithm
isMutlipleOf3(n):
Step 1: Make n positive if n is negative.
Step 2: If number is 0 then return 1
Step 3: If number is 1 then return 0
Step 4: Initialize: oddsCount = 0, evenCount = 0
Step 5: Loop while n != 0
{
Increment oddCount if rightmost bit is set
Right-shift n by 1 bit
Increment evenCount If rightmost bit is set
Right-shift n by 1 bit
}
return isMutlipleOf3(oddCount - evenCount)
Time complexity of this approach would be O(log n)
Implementation
// C++ program to check if n is a multiple of 3 efficiently
#include <bits/stdc++.h>
using namespace std;
int isMultipleOf3(int n)
{
int oddCount = 0, evenCount = 0;
// Make no positive. 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)
oddCount++;
/* If even bit is set then
increment even counter */
if (n & 2)
evenCount++;
n = n >> 2;
}
return isMultipleOf3(abs(oddCount - evenCount));
}
// Main function
int main()
{
int n = 33;
if (isMultipleOf3(n))
printf("%d is multiple of 3", num);
else
printf("%d is not a multiple of 3", num);
return 0;
}