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.
- The number we start with is 99.
- We take the absolute value of the number, which is still 99.
- 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.
- 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).
- We subtract the count of active even bits from the count of active odd bits: 4 - 2 = 2.
- Now, we repeat the process with the result, which is 2 in this case.
- The binary representation of 2 is 10. So, there is 1 active odd bit (1) and 1 active even bit (0).
- We subtract the count of active even bits from the count of active odd bits: 1 - 1 = 0.
- 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
- The
absValue
function returns the absolute value of the input number. - 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. - 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)
{
Multiple task = new Multiple();
// Test Case
task.multipleOfThree(99);
task.multipleOfThree(124);
task.multipleOfThree(21);
task.multipleOfThree(13445);
}
}
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()
{
Multiple task = Multiple();
// Test Case
task.multipleOfThree(99);
task.multipleOfThree(124);
task.multipleOfThree(21);
task.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
// 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)
{
Multiple task = new Multiple();
// Test Case
task.multipleOfThree(99);
task.multipleOfThree(124);
task.multipleOfThree(21);
task.multipleOfThree(13445);
}
}
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()
{
$task = new Multiple();
$task->multipleOfThree(99);
$task->multipleOfThree(124);
$task->multipleOfThree(21);
$task->multipleOfThree(13445);
}
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()
{
var task = new Multiple();
// Test Case
task.multipleOfThree(99);
task.multipleOfThree(124);
task.multipleOfThree(21);
task.multipleOfThree(13445);
}
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() :
task = Multiple()
# Test Case
task.multipleOfThree(99)
task.multipleOfThree(124)
task.multipleOfThree(21)
task.multipleOfThree(13445)
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()
task = Multiple.new()
# Test Case
task.multipleOfThree(99)
task.multipleOfThree(124)
task.multipleOfThree(21)
task.multipleOfThree(13445)
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
task.multipleOfThree(99);
task.multipleOfThree(124);
task.multipleOfThree(21);
task.multipleOfThree(13445);
}
}
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()
{
let task: Multiple = Multiple();
// Test Case
task.multipleOfThree(99);
task.multipleOfThree(124);
task.multipleOfThree(21);
task.multipleOfThree(13445);
}
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
{
var task: Multiple = Multiple();
// Test Case
task.multipleOfThree(99);
task.multipleOfThree(124);
task.multipleOfThree(21);
task.multipleOfThree(13445);
}
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.
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.
New Comment