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:
- Convert the string into individual digits and calculate their sum.
- Check if the sum is divisible by 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 numbernum
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 returntrue
, indicating that the number is divisible by 3. Otherwise, we returnfalse
. - 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:
- Number: "123"
- Sum of digits: 1 + 2 + 3 = 6
- 6 is divisible by 3.
- Output: "Number 123 is divisible by 3".
Similarly, for "93782639377588932984":
- Sum of digits: 9 + 3 + 7 + 8 + ... = 126
- 126 is divisible by 3.
- Output: "Number 93782639377588932984 is divisible by 3".
For "336235332343":
- Sum of digits: 3 + 3 + 6 + 2 + ... = 35
- 35 is not divisible by 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.
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