Posted on by Kalkicode
Code Bit Logic

# Check if number is multiple of 3

The given problem is to determine whether a given number is a multiple of 3 or not. A multiple of 3 is a number that can be evenly divided by 3 without any remainder. We are provided with a C program that aims to solve this problem using bitwise manipulation.

## Explanation with Suitable Example

Let's take a number, say 99, and see how the algorithm works step by step.

2. We take the absolute value of the number, which is still 99.
3. We then count the number of active odd and even bits in the binary representation of 99. An active bit means a bit with the value 1.
4. The binary representation of 99 is 1100011. So, there are 4 active odd bits (1, 1, 1, 1) and 2 active even bits (0, 1).
5. We subtract the count of active even bits from the count of active odd bits: 4 - 2 = 2.
6. Now, we repeat the process with the result, which is 2 in this case.
7. The binary representation of 2 is 10. So, there is 1 active odd bit (1) and 1 active even bit (0).
8. We subtract the count of active even bits from the count of active odd bits: 1 - 1 = 0.
9. Since the result is 0, we return 1, indicating that 99 is a multiple of 3.

## Standard Pseudocode

``````FUNCTION absValue(num)
IF num < 0 THEN
RETURN -num
END IF
RETURN num
END FUNCTION

FUNCTION isMultipleOfThree(num)
SET n = absValue(num)
IF n = 1 THEN
RETURN 0
ELSE IF n = 0 THEN
RETURN 1
ELSE
SET activeEven = 0
SET activeOdd = 0
WHILE n != 0 DO
IF n AND 1 = 1 THEN
activeOdd = activeOdd + 1
END IF
IF n AND 2 = 2 THEN
activeEven = activeEven + 1
END IF
n = n >> 2
END WHILE
RETURN isMultipleOfThree(activeOdd - activeEven)
END IF
END FUNCTION

FUNCTION multipleOfThree(num)
PRINT "Given number: " + num
IF isMultipleOfThree(num) = 1 THEN
PRINT "Is multiple of 3"
ELSE
PRINT "Is Not multiple of 3"
END IF
END FUNCTION

FUNCTION main()
CALL multipleOfThree(99)
CALL multipleOfThree(124)
CALL multipleOfThree(21)
CALL multipleOfThree(13445)
END FUNCTION
``````

## Algorithm Explanation

1. The `absValue` function returns the absolute value of the input number.
2. The `isMultipleOfThree` function calculates the number of active odd and even bits using bitwise operations, then recursively checks the difference between the counts of active odd and even bits until the result is either 0 or 1.
3. The `multipleOfThree` function prints whether the input number is a multiple of 3 or not.

## Code Solution

Here given code implementation process.

``````// C program
// Check if number is multiple of 3
#include <stdio.h>

//  Returns a absolute value
int absValue(int num)
{
if (num < 0)
{
return -num;
}
return num;
}
// Check that given number is a Multiple of 3 or not
int isMultipleOfThree(int num)
{
int n = absValue(num);
if (n == 1)
{
// When n is one
return 0;
}
else if (n == 0)
{
// When n is zero
return 1;
}
else
{
// Use to count active even and odd position bits
int activeEven = 0;
int activeOdd = 0;
// Execute loop until n is not zero
while (n != 0)
{
if ((n & 1) == 1)
{
// When of least significant bit active
activeOdd++;
}
if ((n & 2) == 2)
{
// When of second bits is active from left side
activeEven++;
}
// shift bit left side by 2
n = n >> 2;
}
// Recursively find active bits from of even and odd position
return isMultipleOfThree(activeOdd - activeEven);
}
}
void multipleOfThree(int num)
{
printf("\n Given number : %d", num);
if (isMultipleOfThree(num) == 1)
{
printf("\n Is multiple of 3\n");
}
else
{
printf("\n Is Not multiple of 3\n");
}
}
int main(int argc, char
const *argv[])
{
// Test Case
multipleOfThree(99);
multipleOfThree(124);
multipleOfThree(21);
multipleOfThree(13445);
return 0;
}``````

#### Output

`````` Given number : 99
Is multiple of 3

Given number : 124
Is Not multiple of 3

Given number : 21
Is multiple of 3

Given number : 13445
Is Not multiple of 3``````
``````// Java program
// Check if number is multiple of 3
public class Multiple
{
//  Returns a absolute value
public int absValue(int num)
{
if (num < 0)
{
return -num;
}
return num;
}
// Check that given number is a Multiple of 3 or not
public boolean isMultipleOfThree(int num)
{
int n = absValue(num);
if (n == 1)
{
// When n is one
return false;
}
else if (n == 0)
{
// When n is zero
return true;
}
else
{
// Use to count active even and odd position bits
int activeEven = 0;
int activeOdd = 0;
// Execute loop until n is not zero
while (n != 0)
{
if ((n & 1) == 1)
{
// When of least significant bit active
activeOdd++;
}
if ((n & 2) == 2)
{
// When of second bits is active from left side
activeEven++;
}
// shift bit left side by 2
n = n >> 2;
}
// Recursively find active bits from of even and odd position
return isMultipleOfThree(activeOdd - activeEven);
}
}
public void multipleOfThree(int num)
{
System.out.print("\n Given number : " + num);
if (isMultipleOfThree(num))
{
System.out.print("\n Is multiple of 3\n");
}
else
{
System.out.print("\n Is Not multiple of 3\n");
}
}
public static void main(String[] args)
{
// Test Case
}
}``````

#### Output

`````` Given number : 99
Is multiple of 3

Given number : 124
Is Not multiple of 3

Given number : 21
Is multiple of 3

Given number : 13445
Is Not multiple of 3``````
``````// Include header file
#include <iostream>
using namespace std;

// C++ program
// Check if number is multiple of 3

class Multiple
{
public:
//  Returns a absolute value
int absValue(int num)
{
if (num < 0)
{
return -num;
}
return num;
}
// Check that given number is a Multiple of 3 or not
bool isMultipleOfThree(int num)
{
int n = this->absValue(num);
if (n == 1)
{
// When n is one
return false;
}
else if (n == 0)
{
// When n is zero
return true;
}
else
{
// Use to count active even and odd position bits
int activeEven = 0;
int activeOdd = 0;
// Execute loop until n is not zero
while (n != 0)
{
if ((n &1) == 1)
{
// When of least significant bit active
activeOdd++;
}
if ((n &2) == 2)
{
// When of second bits is active from left side
activeEven++;
}
// shift bit left side by 2
n = n >> 2;
}
// Recursively find active bits from of even and odd position
return this->isMultipleOfThree(activeOdd - activeEven);
}
}
void multipleOfThree(int num)
{
cout << "\n Given number : " << num;
if (this->isMultipleOfThree(num))
{
cout << "\n Is multiple of 3\n";
}
else
{
cout << "\n Is Not multiple of 3\n";
}
}
};
int main()
{
// Test Case
return 0;
}``````

#### Output

`````` Given number : 99
Is multiple of 3

Given number : 124
Is Not multiple of 3

Given number : 21
Is multiple of 3

Given number : 13445
Is Not multiple of 3``````
``````// Include namespace system
using System;
// C# program
// Check if number is multiple of 3
public class Multiple
{
//  Returns a absolute value
public int absValue(int num)
{
if (num < 0)
{
return -num;
}
return num;
}
// Check that given number is a Multiple of 3 or not
public Boolean isMultipleOfThree(int num)
{
int n = absValue(num);
if (n == 1)
{
// When n is one
return false;
}
else if (n == 0)
{
// When n is zero
return true;
}
else
{
// Use to count active even and odd position bits
int activeEven = 0;
int activeOdd = 0;
// Execute loop until n is not zero
while (n != 0)
{
if ((n & 1) == 1)
{
// When of least significant bit active
activeOdd++;
}
if ((n & 2) == 2)
{
// When of second bits is active from left side
activeEven++;
}
// shift bit left side by 2
n = n >> 2;
}
// Recursively find active bits from of even and odd position
return isMultipleOfThree(activeOdd - activeEven);
}
}
public void multipleOfThree(int num)
{
Console.Write("\n Given number : " + num);
if (isMultipleOfThree(num))
{
Console.Write("\n Is multiple of 3\n");
}
else
{
Console.Write("\n Is Not multiple of 3\n");
}
}
public static void Main(String[] args)
{
// Test Case
}
}``````

#### Output

`````` Given number : 99
Is multiple of 3

Given number : 124
Is Not multiple of 3

Given number : 21
Is multiple of 3

Given number : 13445
Is Not multiple of 3``````
``````<?php
// Php program
// Check if number is multiple of 3
class Multiple
{
//  Returns a absolute value
public	function absValue(\$num)
{
if (\$num < 0)
{
return -\$num;
}
return \$num;
}
// Check that given number is a Multiple of 3 or not
public	function isMultipleOfThree(\$num)
{
\$n = \$this->absValue(\$num);
if (\$n == 1)
{
// When n is one
return false;
}
else if (\$n == 0)
{
// When n is zero
return true;
}
else
{
// Use to count active even and odd position bits
\$activeEven = 0;
\$activeOdd = 0;
// Execute loop until n is not zero
while (\$n != 0)
{
if ((\$n & 1) == 1)
{
// When of least significant bit active
\$activeOdd++;
}
if ((\$n & 2) == 2)
{
// When of second bits is active from left side
\$activeEven++;
}
// shift bit left side by 2
\$n = \$n >> 2;
}
// Recursively find active bits from of even and odd position
return \$this->isMultipleOfThree(\$activeOdd - \$activeEven);
}
}
public	function multipleOfThree(\$num)
{
echo "\n Given number : ". \$num;
if (\$this->isMultipleOfThree(\$num))
{
echo "\n Is multiple of 3\n";
}
else
{
echo "\n Is Not multiple of 3\n";
}
}
}

function main()
{
}
main();``````

#### Output

`````` Given number : 99
Is multiple of 3

Given number : 124
Is Not multiple of 3

Given number : 21
Is multiple of 3

Given number : 13445
Is Not multiple of 3``````
``````// Node Js program
// Check if number is multiple of 3
class Multiple
{
//  Returns a absolute value
absValue(num)
{
if (num < 0)
{
return -num;
}
return num;
}
// Check that given number is a Multiple of 3 or not
isMultipleOfThree(num)
{
var n = this.absValue(num);
if (n == 1)
{
// When n is one
return false;
}
else if (n == 0)
{
// When n is zero
return true;
}
else
{
// Use to count active even and odd position bits
var activeEven = 0;
var activeOdd = 0;
// Execute loop until n is not zero
while (n != 0)
{
if ((n & 1) == 1)
{
// When of least significant bit active
activeOdd++;
}
if ((n & 2) == 2)
{
// When of second bits is active from left side
activeEven++;
}
// shift bit left side by 2
n = n >> 2;
}
// Recursively find active bits from of even and odd position
return this.isMultipleOfThree(activeOdd - activeEven);
}
}
multipleOfThree(num)
{
process.stdout.write("\n Given number : " + num);
if (this.isMultipleOfThree(num))
{
process.stdout.write("\n Is multiple of 3\n");
}
else
{
process.stdout.write("\n Is Not multiple of 3\n");
}
}
}

function main()
{
// Test Case
}
main();``````

#### Output

`````` Given number : 99
Is multiple of 3

Given number : 124
Is Not multiple of 3

Given number : 21
Is multiple of 3

Given number : 13445
Is Not multiple of 3``````
``````#  Python 3 program
#  Check if number is multiple of 3
class Multiple :
#   Returns a absolute value
def absValue(self, num) :
if (num < 0) :
return -num

return num

#  Check that given number is a Multiple of 3 or not
def isMultipleOfThree(self, num) :
n = self.absValue(num)
if (n == 1) :
#  When n is one
return False

elif(n == 0) :
#  When n is zero
return True
else :
#  Use to count active even and odd position bits
activeEven = 0
activeOdd = 0
#  Execute loop until n is not zero
while (n != 0) :
if ((n & 1) == 1) :
#  When of least significant bit active
activeOdd += 1

if ((n & 2) == 2) :
#  When of second bits is active from left side
activeEven += 1

#  shift bit left side by 2
n = n >> 2

#  Recursively find active bits from of even and odd position
return self.isMultipleOfThree(activeOdd - activeEven)

def multipleOfThree(self, num) :
print("\n Given number : ", num, end = "")
if (self.isMultipleOfThree(num)) :
print("\n Is multiple of 3")
else :
print("\n Is Not multiple of 3")

def main() :
#  Test Case

if __name__ == "__main__": main()``````

#### Output

`````` Given number :  99
Is multiple of 3

Given number :  124
Is Not multiple of 3

Given number :  21
Is multiple of 3

Given number :  13445
Is Not multiple of 3``````
``````#  Ruby program
#  Check if number is multiple of 3
class Multiple
#   Returns a absolute value
def absValue(num)
if (num < 0)
return -num
end

return num
end

#  Check that given number is a Multiple of 3 or not
def isMultipleOfThree(num)
n = self.absValue(num)
if (n == 1)
#  When n is one
return false
elsif(n == 0)
#  When n is zero
return true
else
#  Use to count active even and odd position bits
activeEven = 0
activeOdd = 0
#  Execute loop until n is not zero
while (n != 0)
if ((n & 1) == 1)
#  When of least significant bit active
activeOdd += 1
end

if ((n & 2) == 2)
#  When of second bits is active from left side
activeEven += 1
end

#  shift bit left side by 2
n = n >> 2
end

#  Recursively find active bits from of even and odd position
return self.isMultipleOfThree(activeOdd - activeEven)
end

end

def multipleOfThree(num)
print("\n Given number : ", num)
if (self.isMultipleOfThree(num))
print("\n Is multiple of 3\n")
else
print("\n Is Not multiple of 3\n")
end

end

end

def main()
#  Test Case
end

main()``````

#### Output

`````` Given number : 99
Is multiple of 3

Given number : 124
Is Not multiple of 3

Given number : 21
Is multiple of 3

Given number : 13445
Is Not multiple of 3
``````
``````// Scala program
// Check if number is multiple of 3
class Multiple
{
//  Returns a absolute value
def absValue(num: Int): Int = {
if (num < 0)
{
return -num;
}
return num;
}
// Check that given number is a Multiple of 3 or not
def isMultipleOfThree(num: Int): Boolean = {
var n: Int = this.absValue(num);
if (n == 1)
{
// When n is one
return false;
}
else if (n == 0)
{
// When n is zero
return true;
}
else
{
// Use to count active even and odd position bits
var activeEven: Int = 0;
var activeOdd: Int = 0;
// Execute loop until n is not zero
while (n != 0)
{
if ((n & 1) == 1)
{
// When of least significant bit active
activeOdd += 1;
}
if ((n & 2) == 2)
{
// When of second bits is active from left side
activeEven += 1;
}
// shift bit left side by 2
n = n >> 2;
}
// Recursively find active bits from of even and odd position
return this.isMultipleOfThree(activeOdd - activeEven);
}
}
def multipleOfThree(num: Int): Unit = {
print("\n Given number : " + num);
if (this.isMultipleOfThree(num))
{
print("\n Is multiple of 3\n");
}
else
{
print("\n Is Not multiple of 3\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Multiple = new Multiple();
// Test Case
}
}``````

#### Output

`````` Given number : 99
Is multiple of 3

Given number : 124
Is Not multiple of 3

Given number : 21
Is multiple of 3

Given number : 13445
Is Not multiple of 3``````
``````// Swift 4 program
// Check if number is multiple of 3
class Multiple
{
//  Returns a absolute value
func absValue(_ num: Int)->Int
{
if (num < 0)
{
return -num;
}
return num;
}
// Check that given number is a Multiple of 3 or not
func isMultipleOfThree(_ num: Int)->Bool
{
var n: Int = self.absValue(num);
if (n == 1)
{
// When n is one
return false;
}
else if (n == 0)
{
// When n is zero
return true;
}
else
{
// Use to count active even and odd position bits
var activeEven: Int = 0;
var activeOdd: Int = 0;
// Execute loop until n is not zero
while (n  != 0)
{
if ((n & 1) == 1)
{
// When of least significant bit active
activeOdd += 1;
}
if ((n & 2) == 2)
{
// When of second bits is active from left side
activeEven += 1;
}
// shift bit left side by 2
n = n >> 2;
}
// Recursively find active bits from of even and odd position
return self.isMultipleOfThree(activeOdd - activeEven);
}
}
func multipleOfThree(_ num: Int)
{
print("\n Given number : ", num, terminator: "");
if (self.isMultipleOfThree(num))
{
print("\n Is multiple of 3");
}
else
{
print("\n Is Not multiple of 3");
}
}
}
func main()
{
// Test Case
}
main();``````

#### Output

`````` Given number :  99
Is multiple of 3

Given number :  124
Is Not multiple of 3

Given number :  21
Is multiple of 3

Given number :  13445
Is Not multiple of 3``````
``````// Kotlin program
// Check if number is multiple of 3
class Multiple
{
//  Returns a absolute value
fun absValue(num: Int): Int
{
if (num < 0)
{
return -num;
}
return num;
}
// Check that given number is a Multiple of 3 or not
fun isMultipleOfThree(num: Int): Boolean
{
var n: Int = this.absValue(num);
if (n == 1)
{
// When n is one
return false;
}
else if (n == 0)
{
// When n is zero
return true;
}
else
{
// Use to count active even and odd position bits
var activeEven: Int = 0;
var activeOdd: Int = 0;
// Execute loop until n is not zero
while (n != 0)
{
if ((n and 1) == 1)
{
// When of least significant bit active
activeOdd += 1;
}
if ((n and 2) == 2)
{
// When of second bits is active from left side
activeEven += 1;
}
// shift bit left side by 2
n = n shr 2;
}

// Recursively find active bits from of even and odd position
return this.isMultipleOfThree(activeOdd - activeEven);
}
}
fun multipleOfThree(num: Int): Unit
{
print("\n Given number : " + num);
if (this.isMultipleOfThree(num))
{
print("\n Is multiple of 3\n");
}
else
{
print("\n Is Not multiple of 3\n");
}
}
}
fun main(args: Array < String > ): Unit
{
// Test Case
}``````

#### Output

`````` Given number : 99
Is multiple of 3

Given number : 124
Is Not multiple of 3

Given number : 21
Is multiple of 3

Given number : 13445
Is Not multiple of 3``````

## Resultant Output Explanation

For each test case, the program calls the `multipleOfThree` function with the given number as input. It then prints whether the number is a multiple of 3 or not.

• For `multipleOfThree(99)`, the output is "Is multiple of 3" because 99 is a multiple of 3.
• For `multipleOfThree(124)`, the output is "Is Not multiple of 3" because 124 is not a multiple of 3.
• For `multipleOfThree(21)`, the output is "Is multiple of 3" because 21 is a multiple of 3.
• For `multipleOfThree(13445)`, the output is "Is Not multiple of 3" because 13445 is not a multiple of 3.

## Time Complexity

The time complexity of this algorithm is O(log n), where n is the absolute value of the input number. This is because the algorithm iterates through the bits of the number using bitwise operations, and the number of bits in the absolute value of the input number is logarithmic with respect to the input number.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post