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.

1. The number we start with is 99.
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
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// 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;
}

 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);
	}
}

 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;
}

 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);
	}
}

 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();

 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();

 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()

 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()

 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);
	}
}

 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();

 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);
}

 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.