Skip to main content

Check if large number is divisible by 3

Divisibility is a fundamental concept in mathematics, and it holds importance in various real-world scenarios. When dealing with large numbers, especially those that cannot be comfortably handled by standard data types like integers or longs, determining their divisibility by another number can be a challenging task. In this article, we'll explore the problem of checking whether a large number is divisible by 3. We'll break down the problem, provide a step-by-step solution, and explain the code implementation in simple terms. By the end of this article, you'll have a clear understanding of how to tackle this problem efficiently.

Problem Statement

Given a large number represented as a string of digits, we want to determine if it's divisible by 3.

Example and Description

Let's take the number "93782639377588932984" as an example. This number is too large to be stored in standard data types, so it's represented as a string. We need to find out if this number is divisible by 3.

Idea to Solve the Problem

To check if a number is divisible by 3, we need to examine its digits' sum. If the sum of the digits is divisible by 3, then the entire number is divisible by 3. We'll follow these steps:

  1. Convert the string into individual digits and calculate their sum.
  2. Check if the sum is divisible by 3.
  3. If the sum is divisible by 3, then the original number is divisible by 3.

Pseudocode

function divisibleBy3(num)
    sum = 0
    for digit in num
        sum += digit
    if sum % 3 == 0
        return true
    else
        return false

Algorithm Explanation

  • We start by defining a function divisibleBy3 that takes the input number num as a string.
  • We initialize a variable sum to store the sum of digits' values.
  • We iterate through each digit in the string. Since the digits are represented as characters, we subtract the ASCII value of '0' to get the actual digit value and add it to the sum.
  • After iterating through all digits, we check if the sum is divisible by 3. If it is, we return true, indicating that the number is divisible by 3. Otherwise, we return false.
  • In the main program, we call the divisibleBy3 function for different test inputs and print the result accordingly.

Code Solution

/*
    C program for
    Check if large number is divisible by 3
*/
#include <stdio.h>

#include <string.h>

void divisibleBy3(const char *num)
{
	// Get the length of number
	int n = strlen(num);
	if (n == 0)
	{
		return;
	}
	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		// Sum of number digits
		sum += num[i] - '0';
	}
	if ((sum % 3) == 0)
	{
		printf("\n Number %s divisible by 3", num);
	}
	else
	{
		printf("\n Number %s is not divisible by 3", num);
	}
}
int main(int argc, char const *argv[])
{
	// Test Inputs
	divisibleBy3("123");
	divisibleBy3("93782639377588932984");
	divisibleBy3("336235332343");
	divisibleBy3("32456613423");
	return 0;
}

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3
/*
    Java program for
    Check if large number is divisible by 3
*/
class Divisibility
{
    public void divisibleBy3(String num)
    {
        // Get the length of number
        int n = num.length();
        if (n == 0)
        {
            return;
        }
        int sum = 0;
        for (int i = 0; i < n; ++i)
        {
            // Sum of number digits
            sum += num.charAt(i) - '0';
        }
        if ((sum % 3) == 0)
        {
            System.out.print("\n Number " + num + " divisible by 3");
        }
        else
        {
            System.out.print("\n Number " + num + " is not divisible by 3");
        }
    }
    public static void main(String[] args)
    {
        Divisibility task = new Divisibility();
        // Test Inputs
        task.divisibleBy3("123");
        task.divisibleBy3("93782639377588932984");
        task.divisibleBy3("336235332343");
        task.divisibleBy3("32456613423");
    }
}

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
    C++ program for
    Check if large number is divisible by 3
*/
class Divisibility
{
	public: void divisibleBy3(string num)
	{
		// Get the length of number
		int n = num.length();
		if (n == 0)
		{
			return;
		}
		int sum = 0;
		for (int i = 0; i < n; ++i)
		{
			// Sum of number digits
			sum += num[i] - '0';
		}
		if ((sum % 3) == 0)
		{
			cout << "\n Number " << num << " divisible by 3";
		}
		else
		{
			cout << "\n Number " << num << " is not divisible by 3";
		}
	}
};
int main()
{
	Divisibility *task = new Divisibility();
	// Test Inputs
	task->divisibleBy3("123");
	task->divisibleBy3("93782639377588932984");
	task->divisibleBy3("336235332343");
	task->divisibleBy3("32456613423");
	return 0;
}

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3
// Include namespace system
using System;
/*
    Csharp program for
    Check if large number is divisible by 3
*/
public class Divisibility
{
	public void divisibleBy3(String num)
	{
		// Get the length of number
		int n = num.Length;
		if (n == 0)
		{
			return;
		}
		int sum = 0;
		for (int i = 0; i < n; ++i)
		{
			// Sum of number digits
			sum += num[i] - '0';
		}
		if ((sum % 3) == 0)
		{
			Console.Write("\n Number " + num + " divisible by 3");
		}
		else
		{
			Console.Write("\n Number " + num + " is not divisible by 3");
		}
	}
	public static void Main(String[] args)
	{
		Divisibility task = new Divisibility();
		// Test Inputs
		task.divisibleBy3("123");
		task.divisibleBy3("93782639377588932984");
		task.divisibleBy3("336235332343");
		task.divisibleBy3("32456613423");
	}
}

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3
package main
import "fmt"
/*
    Go program for
    Check if large number is divisible by 3
*/

func divisibleBy3(num string) {
	// Get the length of number
	var n int = len(num)
	if n == 0 {
		return
	}
	var sum int = 0
	for i := 0 ; i < n ; i++ {
		// Sum of number digits
		sum += int(num[i] - '0')
	}
	if (sum % 3) == 0 {
		fmt.Print("\n Number ", num, " divisible by 3")
	} else {
		fmt.Print("\n Number ", num, " is not divisible by 3")
	}
}
func main() {

	// Test Inputs
	divisibleBy3("123")
	divisibleBy3("93782639377588932984")
	divisibleBy3("336235332343")
	divisibleBy3("32456613423")
}

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3
<?php
/*
    Php program for
    Check if large number is divisible by 3
*/
class Divisibility
{
	public	function divisibleBy3($num)
	{
		// Get the length of number
		$n = strlen($num);
		if ($n == 0)
		{
			return;
		}
		$sum = 0;
		for ($i = 0; $i < $n; ++$i)
		{
			// Sum of number digits
			$sum += ord($num[$i]) - ord('0');
		}
		if (($sum % 3) == 0)
		{
			echo("\n Number ".$num.
				" divisible by 3");
		}
		else
		{
			echo("\n Number ".$num.
				" is not divisible by 3");
		}
	}
}

function main()
{
	$task = new Divisibility();
	// Test Inputs
	$task->divisibleBy3("123");
	$task->divisibleBy3("93782639377588932984");
	$task->divisibleBy3("336235332343");
	$task->divisibleBy3("32456613423");
}
main();

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3
/*
    Node JS program for
    Check if large number is divisible by 3
*/
class Divisibility
{
	divisibleBy3(num)
	{
		// Get the length of number
		var n = num.length;
		if (n == 0)
		{
			return;
		}
		var sum = 0;
		for (var i = 0; i < n; ++i)
		{
			// Sum of number digits
			sum += num.charCodeAt(i) - '0'.charCodeAt(0);
		}
		if ((sum % 3) == 0)
		{
			process.stdout.write("\n Number " + num + " divisible by 3");
		}
		else
		{
			process.stdout.write("\n Number " + num + " is not divisible by 3");
		}
	}
}

function main()
{
	var task = new Divisibility();
	// Test Inputs
	task.divisibleBy3("123");
	task.divisibleBy3("93782639377588932984");
	task.divisibleBy3("336235332343");
	task.divisibleBy3("32456613423");
}
main();

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3
#    Python 3 program for
#    Check if large number is divisible by 3
class Divisibility :
	def divisibleBy3(self, num) :
		#  Get the length of number
		n = len(num)
		if (n == 0) :
			return
		
		sum = 0
		i = 0
		while (i < n) :
			#  Sum of number digits
			sum += ord(num[i]) - ord('0')
			i += 1
		
		if ((sum % 3) == 0) :
			print("\n Number", num ,"divisible by 3", end = "")
		else :
			print("\n Number", num ,"is not divisible by 3", end = "")
		
	

def main() :
	task = Divisibility()
	#  Test Inputs
	task.divisibleBy3("123")
	task.divisibleBy3("93782639377588932984")
	task.divisibleBy3("336235332343")
	task.divisibleBy3("32456613423")

if __name__ == "__main__": main()

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3
#    Ruby program for
#    Check if large number is divisible by 3
class Divisibility 
	def divisibleBy3(num) 
		#  Get the length of number
		n = num.length
		if (n == 0) 
			return
		end

		sum = 0
		i = 0
		while (i < n) 
			#  Sum of number digits
			sum += num[i].ord - '0'.ord
			i += 1
		end

		if ((sum % 3) == 0) 
			print("\n Number ", num ," divisible by 3")
		else
 
			print("\n Number ", num ," is not divisible by 3")
		end

	end

end

def main() 
	task = Divisibility.new()
	#  Test Inputs
	task.divisibleBy3("123")
	task.divisibleBy3("93782639377588932984")
	task.divisibleBy3("336235332343")
	task.divisibleBy3("32456613423")
end

main()

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3
/*
    Scala program for
    Check if large number is divisible by 3
*/
class Divisibility()
{
	def divisibleBy3(num: String): Unit = {
		// Get the length of number
		var n: Int = num.length();
		if (n == 0)
		{
			return;
		}
		var sum: Int = 0;
		var i: Int = 0;
		while (i < n)
		{
			// Sum of number digits
			sum += num.charAt(i).toInt - '0'.toInt;
			i += 1;
		}
		if ((sum % 3) == 0)
		{
			print("\n Number " + num + " divisible by 3");
		}
		else
		{
			print("\n Number " + num + " is not divisible by 3");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Divisibility = new Divisibility();
		// Test Inputs
		task.divisibleBy3("123");
		task.divisibleBy3("93782639377588932984");
		task.divisibleBy3("336235332343");
		task.divisibleBy3("32456613423");
	}
}

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3
import Foundation;
/*
    Swift 4 program for
    Check if large number is divisible by 3
*/
class Divisibility
{
	func divisibleBy3(_ data: String)
	{
      	let num = Array(data);
		// Get the length of number
		let n: Int = num.count;
		if (n == 0)
		{
			return;
		}
		var sum: Int = 0;
		var i: Int = 0;
		while (i < n)
		{
			// Sum of number digits
			sum += Int(UnicodeScalar(String(num[i]))!.value) - 
              Int(UnicodeScalar(String("0"))!.value);
			i += 1;
		}
		if ((sum % 3) == 0)
		{
			print("\n Number", data ,"divisible by 3", terminator: "");
		}
		else
		{
			print("\n Number", data ,"is not divisible by 3", terminator: "");
		}
	}
}
func main()
{
	let task: Divisibility = Divisibility();
	// Test Inputs
	task.divisibleBy3("123");
	task.divisibleBy3("93782639377588932984");
	task.divisibleBy3("336235332343");
	task.divisibleBy3("32456613423");
}
main();

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3
/*
    Kotlin program for
    Check if large number is divisible by 3
*/
class Divisibility
{
	fun divisibleBy3(num: String): Unit
	{
		// Get the length of number
		val n: Int = num.length;
		if (n == 0)
		{
			return;
		}
		var sum: Int = 0;
		var i: Int = 0;
		while (i < n)
		{
			// Sum of number digits
			sum += num.get(i).toInt() - '0'.toInt();
			i += 1;
		}
		if ((sum % 3) == 0)
		{
			print("\n Number " + num + " divisible by 3");
		}
		else
		{
			print("\n Number " + num + " is not divisible by 3");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Divisibility = Divisibility();
	// Test Inputs
	task.divisibleBy3("123");
	task.divisibleBy3("93782639377588932984");
	task.divisibleBy3("336235332343");
	task.divisibleBy3("32456613423");
}

Output

 Number 123 divisible by 3
 Number 93782639377588932984 divisible by 3
 Number 336235332343 is not divisible by 3
 Number 32456613423 divisible by 3

Explanation

Let's take the example of the number "123" and walk through the algorithm:

  1. Number: "123"
  2. Sum of digits: 1 + 2 + 3 = 6
  3. 6 is divisible by 3.
  4. Output: "Number 123 is divisible by 3".

Similarly, for "93782639377588932984":

  1. Sum of digits: 9 + 3 + 7 + 8 + ... = 126
  2. 126 is divisible by 3.
  3. Output: "Number 93782639377588932984 is divisible by 3".

For "336235332343":

  1. Sum of digits: 3 + 3 + 6 + 2 + ... = 35
  2. 35 is not divisible by 3.
  3. Output: "Number 336235332343 is not divisible by 3".

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of digits in the input number. This is because we iterate through each digit once to calculate the sum.





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