Skip to main content

DFA based division

DFA (Deterministic Finite Automaton) is a concept from automata theory that deals with modeling and analyzing finite state machines. In this context, "DFA-based division" refers to a method of performing division using a finite state machine. This approach is an interesting way to solve the division problem by modeling it as a state transition process.

Problem Statement

The problem is to implement a division algorithm using a DFA (Deterministic Finite Automaton) approach. Given two positive integers, a dividend and a divisor, the goal is to determine whether the dividend is divisible by the divisor and calculate the remainder if it's not divisible.

Idea to Solve the Problem

The idea is to treat the division process as a state transition in a deterministic finite automaton. Each state of the automaton corresponds to a partial remainder, and the transitions between states are determined by the bits of the dividend as they are processed one by one.

Pseudocode

function checkState(dividend, remainder, transaction)
    if dividend != 0
        checkState(dividend >> 1, remainder, transaction)
        remainder = transaction[remainder][dividend & 1]

function divide(dividend, divisor)
    if divisor <= 0
        return
    
    create transaction[divisor][2]
    zero = 0
    one = 0
    remainder = 0
    
    for state from 0 to divisor - 1
        zero = state << 1
        one = zero + 1
        if zero < divisor
            transaction[state][0] = zero
        else
            transaction[state][0] = zero - divisor
        if one < divisor
            transaction[state][1] = one
        else
            transaction[state][1] = one - divisor
    
    checkState(dividend, remainder, transaction)
    
    if remainder == 0
        print "(", dividend, " / ", divisor, ") Are Divisible \n\n"
    else
        print "(", dividend, " / ", divisor, ") are not divisible \n"
        print "Remainder is: ", remainder, "\n\n"

Algorithm Explanation

  1. The checkState function is a recursive function that calculates the remainder of the division by traversing the bits of the dividend from the most significant to the least significant. It uses the transaction array to determine the next state based on the current bit.

  2. The divide function takes the dividend and divisor as inputs. It initializes the transaction array and sets up the DFA's states and transitions.

  3. The nested loop creates transitions for each state. If the transition leads to a state greater than or equal to divisor, it adjusts the state to be within the valid range.

  4. The checkState function is then called to calculate the remainder using the DFA transitions.

  5. Based on the remainder calculated, the function prints whether the dividend is divisible by the divisor along with the remainder, if applicable.

Program Solution

// C program for 
// DFA based division
#include <stdio.h>

// Recursively, find the remainder of divisor
void checkState(int dividend, int *remainder, int transaction[][2])
{
	if (dividend != 0)
	{
		checkState(dividend >> 1, remainder, transaction);*remainder = transaction[ *remainder][dividend & 1];
	}
}
void divide(int dividend, int divisor)
{
	if (divisor <= 0)
	{
		// That is not working when divisor is negative
		return;
	}
	// Use to collect transaction
	int transaction[divisor][2];
	// Define useful variables
	int zero = 0;
	int one = 0;
	int remainder = 0;
	// Execute loop through by given divisor
	for (int state = 0; state < divisor; ++state)
	{
		// Next state for bit zero
		zero = state << 1;
		// Next state for bit one
		one = zero + 1;
		if (zero < divisor)
		{
			transaction[state][0] = zero;
		}
		else
		{
			transaction[state][0] = zero - divisor;
		}
		if (one < divisor)
		{
			transaction[state][1] = one;
		}
		else
		{
			transaction[state][1] = one - divisor;
		}
	}
	// Check remainder
	checkState(dividend, & remainder, transaction);
	if (remainder == 0)
	{
		printf(" (%d / %d) Are Divisible \n\n", dividend, divisor);
	}
	else
	{
		printf(" (%d / %d) are not divisible \n", dividend, divisor);
		printf(" Remainder is : %d\n\n", remainder);
	}
}
int main(int argc, char
	const *argv[])
{
	// Test Case 
	divide(21, 6);
	divide(25, 5);
	divide(14, 7);
	divide(34, 3);
	divide(54, 3);
	return 0;
}

input

 (21 / 6) are not divisible
 Remainder is : 3

 (25 / 5) Are Divisible

 (14 / 7) Are Divisible

 (34 / 3) are not divisible
 Remainder is : 1

 (54 / 3) Are Divisible

/*
  Java Program for
  DFA based division
*/
public class DFAdivision
{
	int remainder;
	public DFAdivision()
	{
		this.remainder = 0;
	}
	// Recursively, find the remainder of divisor
	public void checkState(int dividend, int[][] transaction)
	{
		if (dividend != 0)
		{
			checkState(dividend >> 1, transaction);
			this.remainder = transaction[this.remainder][dividend & 1];
		}
	}
	public void divide(int dividend, int divisor)
	{
		if (divisor <= 0)
		{
			// That is not working when divisor is negative
			return;
		}
		// Use to collect transaction
		int[][] transaction = new int[divisor][2];
		// Define useful variables
		int zero = 0;
		int one = 0;
		// Execute loop through by given divisor
		for (int state = 0; state < divisor; ++state)
		{
			// Next state for bit zero
			zero = state << 1;
			// Next state for bit one
			one = zero + 1;
			if (zero < divisor)
			{
				transaction[state][0] = zero;
			}
			else
			{
				transaction[state][0] = zero - divisor;
			}
			if (one < divisor)
			{
				transaction[state][1] = one;
			}
			else
			{
				transaction[state][1] = one - divisor;
			}
		}
		this.remainder = 0;
		// Check remainder
		checkState(dividend, transaction);
		if (this.remainder == 0)
		{
			System.out.println(" (" + dividend + " / " + divisor + ") Are Divisible \n");
		}
		else
		{
			System.out.print(" (" + dividend + " / " + divisor + ") are not divisible \n");
			System.out.println(" Remainder is : " + this.remainder + "\n");
		}
	}
	public static void main(String[] args)
	{
		DFAdivision task = new DFAdivision();
		// Test Case 
		task.divide(21, 6);
		task.divide(25, 5);
		task.divide(14, 7);
		task.divide(34, 3);
		task.divide(54, 3);
	}
}

input

 (21 / 6) are not divisible
 Remainder is : 3

 (25 / 5) Are Divisible

 (14 / 7) Are Divisible

 (34 / 3) are not divisible
 Remainder is : 1

 (54 / 3) Are Divisible

// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program for
  DFA based division
*/
class DFAdivision
{
	public: int remainder;
	DFAdivision()
	{
		this->remainder = 0;
	}
	// Recursively, find the remainder of divisor
	void checkState(int dividend, int transaction[][2])
	{
		if (dividend != 0)
		{
			this->checkState(dividend >> 1, transaction);
			this->remainder = transaction[this->remainder][dividend &1];
		}
	}
	void divide(int dividend, int divisor)
	{
		if (divisor <= 0)
		{
			// That is not working when divisor is negative
			return;
		}
		// Use to collect transaction
		int transaction[divisor][2];
		// Define useful variables
		int zero = 0;
		int one = 0;
		// Execute loop through by given divisor
		for (int state = 0; state < divisor; ++state)
		{
			// Next state for bit zero
			zero = state << 1;
			// Next state for bit one
			one = zero + 1;
			if (zero < divisor)
			{
				transaction[state][0] = zero;
			}
			else
			{
				transaction[state][0] = zero - divisor;
			}
			if (one < divisor)
			{
				transaction[state][1] = one;
			}
			else
			{
				transaction[state][1] = one - divisor;
			}
		}
		this->remainder = 0;
		// Check remainder
		this->checkState(dividend, transaction);
		if (this->remainder == 0)
		{
			cout << " (" << dividend << " / " << divisor << ") Are Divisible \n" << endl;
		}
		else
		{
			cout << " (" << dividend << " / " << divisor << ") are not divisible \n";
			cout << " Remainder is : " << this->remainder << "\n" << endl;
		}
	}
};
int main()
{
	DFAdivision *task = new DFAdivision();
	// Test Case 
	task->divide(21, 6);
	task->divide(25, 5);
	task->divide(14, 7);
	task->divide(34, 3);
	task->divide(54, 3);
	return 0;
}

input

 (21 / 6) are not divisible
 Remainder is : 3

 (25 / 5) Are Divisible

 (14 / 7) Are Divisible

 (34 / 3) are not divisible
 Remainder is : 1

 (54 / 3) Are Divisible

// Include namespace system
using System;
/*
  Csharp Program for
  DFA based division
*/
public class DFAdivision
{
	int remainder;
	public DFAdivision()
	{
		this.remainder = 0;
	}
	// Recursively, find the remainder of divisor
	public void checkState(int dividend, int[,] transaction)
	{
		if (dividend != 0)
		{
			this.checkState(dividend >> 1, transaction);
			this.remainder = transaction[this.remainder,dividend & 1];
		}
	}
	public void divide(int dividend, int divisor)
	{
		if (divisor <= 0)
		{
			// That is not working when divisor is negative
			return;
		}
		// Use to collect transaction
		int[,] transaction = new int[divisor,2];
		// Define useful variables
		int zero = 0;
		int one = 0;
		// Execute loop through by given divisor
		for (int state = 0; state < divisor; ++state)
		{
			// Next state for bit zero
			zero = state << 1;
			// Next state for bit one
			one = zero + 1;
			if (zero < divisor)
			{
				transaction[state,0] = zero;
			}
			else
			{
				transaction[state,0] = zero - divisor;
			}
			if (one < divisor)
			{
				transaction[state,1] = one;
			}
			else
			{
				transaction[state,1] = one - divisor;
			}
		}
		this.remainder = 0;
		// Check remainder
		this.checkState(dividend, transaction);
		if (this.remainder == 0)
		{
			Console.WriteLine(" (" + dividend + " / " + divisor + ") Are Divisible \n");
		}
		else
		{
			Console.Write(" (" + dividend + " / " + divisor + ") are not divisible \n");
			Console.WriteLine(" Remainder is : " + this.remainder + "\n");
		}
	}
	public static void Main(String[] args)
	{
		DFAdivision task = new DFAdivision();
		// Test Case 
		task.divide(21, 6);
		task.divide(25, 5);
		task.divide(14, 7);
		task.divide(34, 3);
		task.divide(54, 3);
	}
}

input

 (21 / 6) are not divisible
 Remainder is : 3

 (25 / 5) Are Divisible

 (14 / 7) Are Divisible

 (34 / 3) are not divisible
 Remainder is : 1

 (54 / 3) Are Divisible

<?php
/*
  Php Program for
  DFA based division
*/
class DFAdivision
{
	public $remainder;
	public	function __construct()
	{
		$this->remainder = 0;
	}
	// Recursively, find the remainder of divisor
	public	function checkState($dividend, $transaction)
	{
		if ($dividend != 0)
		{
			$this->checkState($dividend >> 1, $transaction);
			$this->remainder = $transaction[$this->remainder][$dividend & 1];
		}
	}
	public	function divide($dividend, $divisor)
	{
		if ($divisor <= 0)
		{
			// That is not working when divisor is negative
			return;
		}
		// Use to collect transaction
		$transaction = array_fill(0, 2, array_fill(0, $divisor, 0));
		// Define useful variables
		$zero = 0;
		$one = 0;
		// Execute loop through by given divisor
		for ($state = 0; $state < $divisor; ++$state)
		{
			// Next state for bit zero
			$zero = $state << 1;
			// Next state for bit one
			$one = $zero + 1;
			if ($zero < $divisor)
			{
				$transaction[$state][0] = $zero;
			}
			else
			{
				$transaction[$state][0] = $zero - $divisor;
			}
			if ($one < $divisor)
			{
				$transaction[$state][1] = $one;
			}
			else
			{
				$transaction[$state][1] = $one - $divisor;
			}
		}
		$this->remainder = 0;
		// Check remainder
		$this->checkState($dividend, $transaction);
		if ($this->remainder == 0)
		{
			echo " (".$dividend." / ".$divisor.") Are Divisible \n\n";
		}
		else
		{
			echo " (".$dividend." / ".$divisor.") are not divisible \n";
			echo " Remainder is : ".$this->remainder."\n"."\n";
		}
	}
}

function main()
{
	$task = new DFAdivision();
	// Test Case 
	$task->divide(21, 6);
	$task->divide(25, 5);
	$task->divide(14, 7);
	$task->divide(34, 3);
	$task->divide(54, 3);
}
main();

input

 (21 / 6) are not divisible
 Remainder is : 3

 (25 / 5) Are Divisible

 (14 / 7) Are Divisible

 (34 / 3) are not divisible
 Remainder is : 1

 (54 / 3) Are Divisible

/*
  Node JS Program for
  DFA based division
*/
class DFAdivision
{
	constructor()
	{
		this.remainder = 0;
	}
	// Recursively, find the remainder of divisor
	checkState(dividend, transaction)
	{
		if (dividend != 0)
		{
			this.checkState(dividend >> 1, transaction);
			this.remainder = transaction[this.remainder][dividend & 1];
		}
	}
	divide(dividend, divisor)
	{
		if (divisor <= 0)
		{
			// That is not working when divisor is negative
			return;
		}
		// Use to collect transaction
		var transaction = Array(divisor).fill(0).map(() => new Array(2).fill(0));
		// Define useful variables
		var zero = 0;
		var one = 0;
		// Execute loop through by given divisor
		for (var state = 0; state < divisor; ++state)
		{
			// Next state for bit zero
			zero = state << 1;
			// Next state for bit one
			one = zero + 1;
			if (zero < divisor)
			{
				transaction[state][0] = zero;
			}
			else
			{
				transaction[state][0] = zero - divisor;
			}
			if (one < divisor)
			{
				transaction[state][1] = one;
			}
			else
			{
				transaction[state][1] = one - divisor;
			}
		}
		this.remainder = 0;
		// Check remainder
		this.checkState(dividend, transaction);
		if (this.remainder == 0)
		{
			console.log(" (" + dividend + " / " + divisor + ") Are Divisible \n");
		}
		else
		{
			process.stdout.write(" (" + dividend + " / " + divisor + ") are not divisible \n");
			console.log(" Remainder is : " + this.remainder + "\n");
		}
	}
}

function main()
{
	var task = new DFAdivision();
	// Test Case 
	task.divide(21, 6);
	task.divide(25, 5);
	task.divide(14, 7);
	task.divide(34, 3);
	task.divide(54, 3);
}
main();

input

 (21 / 6) are not divisible
 Remainder is : 3

 (25 / 5) Are Divisible

 (14 / 7) Are Divisible

 (34 / 3) are not divisible
 Remainder is : 1

 (54 / 3) Are Divisible

#  Python 3 Program for
#  DFA based division
class DFAdivision :
	def __init__(self) :
		self.remainder = 0
	
	#  Recursively, find the remainder of divisor
	def checkState(self, dividend, transaction) :
		if (dividend != 0) :
			self.checkState(dividend >> 1, transaction)
			self.remainder = transaction[self.remainder][dividend & 1]
		
	
	def divide(self, dividend, divisor) :
		if (divisor <= 0) :
			#  That is not working when divisor is negative
			return
		
		transaction = [[0] * (2) for _ in range(divisor) ]
		zero = 0
		one = 0
		#  Execute loop through by given divisor
		state = 0
		while (state < divisor) :
			#  Next state for bit zero
			zero = state << 1
			#  Next state for bit one
			one = zero + 1
			if (zero < divisor) :
				transaction[state][0] = zero
			else :
				transaction[state][0] = zero - divisor
			
			if (one < divisor) :
				transaction[state][1] = one
			else :
				transaction[state][1] = one - divisor
			
			state += 1
		
		self.remainder = 0
		#  Check remainder
		self.checkState(dividend, transaction)
		if (self.remainder == 0) :
			print(" (", dividend ," / ", divisor ,") Are Divisible \n")
		else :
			print(" (", dividend ," / ", divisor ,") are not divisible ")
			print(" Remainder is : ", self.remainder ,"\n")
		
	

def main() :
	task = DFAdivision()
	#  Test Case 
	task.divide(21, 6)
	task.divide(25, 5)
	task.divide(14, 7)
	task.divide(34, 3)
	task.divide(54, 3)

if __name__ == "__main__": main()

input

 ( 21  /  6 ) are not divisible
 Remainder is :  3

 ( 25  /  5 ) Are Divisible

 ( 14  /  7 ) Are Divisible

 ( 34  /  3 ) are not divisible
 Remainder is :  1

 ( 54  /  3 ) Are Divisible

#  Ruby Program for
#  DFA based division
class DFAdivision 
	# Define the accessor and reader of class DFAdivision
	attr_reader :remainder
	attr_accessor :remainder
	def initialize() 
		self.remainder = 0
	end

	#  Recursively, find the remainder of divisor
	def checkState(dividend, transaction) 
		if (dividend != 0) 
			self.checkState(dividend >> 1, transaction)
			self.remainder = transaction[self.remainder][dividend & 1]
		end

	end

	def divide(dividend, divisor) 
		if (divisor <= 0) 
			#  That is not working when divisor is negative
			return
		end

		#  Use to collect transaction
		transaction = Array.new(divisor) {Array.new(2) {0}}
		#  Define useful variables
		zero = 0
		one = 0
		#  Execute loop through by given divisor
		state = 0
		while (state < divisor) 
			#  Next state for bit zero
			zero = state << 1
			#  Next state for bit one
			one = zero + 1
			if (zero < divisor) 
				transaction[state][0] = zero
			else 
				transaction[state][0] = zero - divisor
			end

			if (one < divisor) 
				transaction[state][1] = one
			else 
				transaction[state][1] = one - divisor
			end

			state += 1
		end

		self.remainder = 0
		#  Check remainder
		self.checkState(dividend, transaction)
		if (self.remainder == 0) 
			print(" (", dividend ," / ", divisor ,") Are Divisible \n", "\n")
		else 
			print(" (", dividend ," / ", divisor ,") are not divisible \n")
			print(" Remainder is : ", self.remainder ,"\n", "\n")
		end

	end

end

def main() 
	task = DFAdivision.new()
	#  Test Case 
	task.divide(21, 6)
	task.divide(25, 5)
	task.divide(14, 7)
	task.divide(34, 3)
	task.divide(54, 3)
end

main()

input

 (21 / 6) are not divisible 
 Remainder is : 3

 (25 / 5) Are Divisible 

 (14 / 7) Are Divisible 

 (34 / 3) are not divisible 
 Remainder is : 1

 (54 / 3) Are Divisible 


/*
  Scala Program for
  DFA based division
*/
class DFAdivision(var remainder: Int)
{
	def this()
	{
		this(0);
	}
	// Recursively, find the remainder of divisor
	def checkState(dividend: Int, transaction: Array[Array[Int]]): Unit = {
		if (dividend != 0)
		{
			checkState(dividend >> 1, transaction);
			this.remainder = transaction(this.remainder)(dividend & 1);
		}
	}
	def divide(dividend: Int, divisor: Int): Unit = {
		if (divisor <= 0)
		{
			// That is not working when divisor is negative
			return;
		}
		// Use to collect transaction
		var transaction: Array[Array[Int]] = Array.fill[Int](divisor, 2)(0);
		// Define useful variables
		var zero: Int = 0;
		var one: Int = 0;
		// Execute loop through by given divisor
		var state: Int = 0;
		while (state < divisor)
		{
			// Next state for bit zero
			zero = state << 1;
			// Next state for bit one
			one = zero + 1;
			if (zero < divisor)
			{
				transaction(state)(0) = zero;
			}
			else
			{
				transaction(state)(0) = zero - divisor;
			}
			if (one < divisor)
			{
				transaction(state)(1) = one;
			}
			else
			{
				transaction(state)(1) = one - divisor;
			}
			state += 1;
		}
		this.remainder = 0;
		// Check remainder
		checkState(dividend, transaction);
		if (this.remainder == 0)
		{
			println(" (" + dividend + " / " + divisor + ") Are Divisible \n");
		}
		else
		{
			print(" (" + dividend + " / " + divisor + ") are not divisible \n");
			println(" Remainder is : " + this.remainder + "\n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: DFAdivision = new DFAdivision();
		// Test Case 
		task.divide(21, 6);
		task.divide(25, 5);
		task.divide(14, 7);
		task.divide(34, 3);
		task.divide(54, 3);
	}
}

input

 (21 / 6) are not divisible
 Remainder is : 3

 (25 / 5) Are Divisible

 (14 / 7) Are Divisible

 (34 / 3) are not divisible
 Remainder is : 1

 (54 / 3) Are Divisible

/*
  Swift 4 Program for
  DFA based division
*/
class DFAdivision
{
	var remainder: Int;
	init()
	{
		self.remainder = 0;
	}
	// Recursively, find the remainder of divisor
	func checkState(_ dividend: Int, _ transaction: [
		[Int]
	])
	{
		if (dividend  != 0)
		{
			self.checkState(dividend >> 1, transaction);
			self.remainder = transaction[self.remainder][dividend & 1];
		}
	}
	func divide(_ dividend: Int, _ divisor: Int)
	{
		if (divisor <= 0)
		{
			// That is not working when divisor is negative
			return;
		}
		// Use to collect transaction
		var transaction: [[Int]] = 
          Array(repeating: Array(repeating: 0, count: 2), count: divisor);
		// Define useful variables
		var zero: Int = 0;
		var one: Int = 0;
		// Execute loop through by given divisor
		var state: Int = 0;
		while (state < divisor)
		{
			// Next state for bit zero
			zero = state << 1;
			// Next state for bit one
			one = zero + 1;
			if (zero < divisor)
			{
				transaction[state][0] = zero;
			}
			else
			{
				transaction[state][0] = zero - divisor;
			}
			if (one < divisor)
			{
				transaction[state][1] = one;
			}
			else
			{
				transaction[state][1] = one - divisor;
			}
			state += 1;
		}
		self.remainder = 0;
		// Check remainder
		self.checkState(dividend, transaction);
		if (self.remainder == 0)
		{
			print(" (", dividend ," / ", divisor ,") Are Divisible \n");
		}
		else
		{
			print(" (", dividend ," / ", divisor ,") are not divisible ");
			print(" Remainder is : ", self.remainder ,"\n");
		}
	}
}
func main()
{
	let task: DFAdivision = DFAdivision();
	// Test Case 
	task.divide(21, 6);
	task.divide(25, 5);
	task.divide(14, 7);
	task.divide(34, 3);
	task.divide(54, 3);
}
main();

input

 ( 21  /  6 ) are not divisible
 Remainder is :  3

 ( 25  /  5 ) Are Divisible

 ( 14  /  7 ) Are Divisible

 ( 34  /  3 ) are not divisible
 Remainder is :  1

 ( 54  /  3 ) Are Divisible

/*
  Kotlin Program for
  DFA based division
*/
class DFAdivision
{
	var remainder: Int;
	constructor()
	{
		this.remainder = 0;
	}
	// Recursively, find the remainder of divisor
	fun checkState(dividend: Int, transaction: Array < Array < Int >> ): Unit
	{
		if (dividend != 0)
		{
			this.checkState(dividend shr 1, transaction);
			this.remainder = transaction[this.remainder][dividend and 1];
		}
	}
	fun divide(dividend: Int, divisor: Int): Unit
	{
		if (divisor <= 0)
		{
			// That is not working when divisor is negative
			return;
		}
		// Use to collect transaction
		val transaction: Array < Array < Int >> = Array(divisor)
		{
			Array(2)
			{
				0
			}
		};
		// Define useful variables
		var zero: Int ;
		var one: Int;
		var state: Int = 0;
		while (state < divisor)
		{
			// Next state for bit zero
			zero = state shl 1;
			// Next state for bit one
			one = zero + 1;
			if (zero < divisor)
			{
				transaction[state][0] = zero;
			}
			else
			{
				transaction[state][0] = zero - divisor;
			}
			if (one < divisor)
			{
				transaction[state][1] = one;
			}
			else
			{
				transaction[state][1] = one - divisor;
			}
			state += 1;
		}
		this.remainder = 0;
		// Check remainder
		this.checkState(dividend, transaction);
		if (this.remainder == 0)
		{
			println(" (" + dividend + " / " + divisor + ") Are Divisible \n");
		}
		else
		{
			print(" (" + dividend + " / " + divisor + ") are not divisible \n");
			println(" Remainder is : " + this.remainder + "\n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: DFAdivision = DFAdivision();
	// Test Case 
	task.divide(21, 6);
	task.divide(25, 5);
	task.divide(14, 7);
	task.divide(34, 3);
	task.divide(54, 3);
}

input

 (21 / 6) are not divisible
 Remainder is : 3

 (25 / 5) Are Divisible

 (14 / 7) Are Divisible

 (34 / 3) are not divisible
 Remainder is : 1

 (54 / 3) Are Divisible

Resultant Output Explanation

Let's analyze the output of the provided code:

(21 / 6) are not divisible
Remainder is: 3

(25 / 5) Are Divisible

(14 / 7) Are Divisible

(34 / 3) are not divisible
Remainder is: 1

(54 / 3) Are Divisible

The output consists of two parts: the first part indicates whether the dividend is divisible by the divisor, and the second part shows the remainder if the division is not exact.

For example, when dividing 21 by 6, the output indicates that 21 is not divisible by 6, and the remainder is 3.

Time Complexity

The time complexity of this algorithm depends on the number of bits in the dividend. Since each bit is processed once, the time complexity is O(log N), where N is the value of the dividend.

Last updated on by Kalkicode




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.

New Comment