Posted on by Kalkicode
Code Mathematics

# Check that if large number is divisible by 13

In this article, we will discuss a problem related to divisibility of large numbers. The task is to determine whether a given large number is divisible by 13. We will explain the problem statement, provide an example for better understanding, present the algorithm and pseudocode with an explanation, and finally, explain the resultant output with the time complexity of the code.

## Problem Statement

The problem is to check whether a large number, represented as a string, is divisible by 13. The given number can have up to billions of digits. We need to determine if the number is divisible by 13 or not.

### Example

Let's consider an example to illustrate the problem. Suppose we have a number "45645645". We want to check if this number is divisible by 13. In this case, the number is not divisible by 13. On the other hand, if we consider a number "6576534533439", it is divisible by 13.

## Algorithm

Here is the algorithm to check if a large number is divisible by 13:

1. Initialize a boolean variable 'result' as false.
2. Initialize a variable 'sum' to store the cumulative sum of the digits.
3. Initialize a variable 'sign' as 1 to alternate the sign of the digits.
4. Initialize a variable 'temp' to store the temporary value of the digits.
5. Check if the length of the number is 1 and the first character is '0'. If true, set 'result' as true.
6. If the length of the number is greater than 1, perform the following steps:
1. If the length of the number divided by 3 gives a remainder of 2, add one or two leading zeros to the number, depending on the remainder.
2. Get the new length of the number after adding leading zeros.
3. Iterate through the number from the end:
1. Extract three digits at a time and convert them to an integer value.
2. Update the 'sum' by adding the temporary value of the digits multiplied by the 'sign'.
3. Alternate the sign by multiplying 'sign' with -1.
4. Check if the absolute value of 'sum' divided by 13 gives a remainder of 0. If true, set 'result' as true.
7. If 'result' is true, print that the given number is divisible by 13. Otherwise, print that it is not divisible by 13.

## Pseudocode

```Function isDivisibleBy13(num: string)
result = false
sum = 0
sign = 1
temp = 0
auxiliary = num
length = length of auxiliary

If length = 1 and num[0] = '0' Then
result = true

If length > 1 Then
If (length % 3) = 2 Then
auxiliary = "0" + auxiliary
Else If (length % 3) = 1 Then
auxiliary = "00" + auxiliary

length = length of auxiliary

For i = length - 1 To 0 Step -1
temp = (auxiliary[i] - 48)
i = i - 1
temp = temp + (auxiliary[i] - 48) * 10
i = i - 1
temp = temp + (auxiliary[i] - 48) * 100
sum = sum + (temp * sign)
sign = sign * -1

If (absValue(sum) % 13) = 0 Then
result = true

If result Then
Print "Given number (" + num + ") is divisible by 13"
Else
Print "Given number (" + num + ") is not divisible by 13"

Function absValue(x: int)
If x < 0 Then
Return -x

Return x
```

## Code Solution

``````// Java program for
// Check that if large number is divisible by 13
public class Divisibility
{
public int absValue(int x)
{
if (x < 0)
{
return -x;
}
return x;
}
public void isDivisibleBy13(String num)
{
boolean result = false;
int sum = 0;
int sign = 1;
int temp = 0;
String auxiliary = num;
int length = auxiliary.length();
if (length == 1 && num.charAt(0) == '0')
{
// When number is zero
result = true;
}
else if(length > 1)
{
if ((length % 3) == 2)
{
// When length divide by 3 remainder is 2
// Mean need to add one more digit
auxiliary = "0" + auxiliary;
}
else if ((length % 3) == 1)
{
// Mean need to add two more digit
auxiliary = "00" + auxiliary;
}
// Get new length
length = auxiliary.length();
for (int i = length - 1; i >= 0; --i)
{
temp = (auxiliary.charAt(i) - 48);
i--;
temp += (auxiliary.charAt(i) - 48) * 10;
i--;
temp += (auxiliary.charAt(i) - 48) * 100;
sum += (temp * sign);
sign = sign * -1;
}
if ((absValue(sum) % 13) == 0)
{
result = true;
}
}
if (result)
{
System.out.println(" Given number (" +
num + ") is divisible by 13");
}
else
{
System.out.println(" Given number (" +
num + ") is not divisible by 13");
}
}
public static void main(String[] args)
{
// Test
}
}``````

#### Output

`````` Given number (45645645) is not divisible by 13
Given number (6576534533439) is divisible by 13
Given number (34965) is not divisible by 13
Given number (56456423434545645567567567867867) is not divisible by 13
Given number (9999912) is divisible by 13``````
``````// Include header file
#include <iostream>
#include <string>

using namespace std;
// C++ program for
// Check that if large number is divisible by 13
class Divisibility
{
public: int absValue(int x)
{
if (x < 0)
{
return -x;
}
return x;
}
void isDivisibleBy13(string num)
{
bool result = false;
int sum = 0;
int sign = 1;
int temp = 0;
string auxiliary = num;
int length = auxiliary.length();
if (length == 1 && num[0] == '0')
{
// When number is zero
result = true;
}
else if (length > 1)
{
if ((length % 3) == 2)
{
// When length divide by 3 remainder is 2
// Mean need to add one more digit
auxiliary = "0" +  auxiliary;
}
else if ((length % 3) == 1)
{
// Mean need to add two more digit
auxiliary = "00" +  auxiliary;
}
// Get new length
length = auxiliary.length();
for (int i = length - 1; i >= 0; --i)
{
temp = (auxiliary[i] - 48);
i--;
temp += (auxiliary[i] - 48) *10;
i--;
temp += (auxiliary[i] - 48) *100;
sum += (temp *sign);
sign = sign *-1;
}
if ((this->absValue(sum) % 13) == 0)
{
result = true;
}
}
if (result)
{
cout << " Given number ("
<< num << ") is divisible by 13" << endl;
}
else
{
cout << " Given number ("
<< num << ") is not divisible by 13" << endl;
}
}
};
int main()
{
// Test
return 0;
}``````

#### Output

`````` Given number (45645645) is not divisible by 13
Given number (6576534533439) is divisible by 13
Given number (34965) is not divisible by 13
Given number (56456423434545645567567567867867) is not divisible by 13
Given number (9999912) is divisible by 13``````
``````// Include namespace system
using System;
// Csharp program for
// Check that if large number is divisible by 13
public class Divisibility
{
public int absValue(int x)
{
if (x < 0)
{
return -x;
}
return x;
}
public void isDivisibleBy13(String num)
{
Boolean result = false;
int sum = 0;
int sign = 1;
int temp = 0;
String auxiliary = num;
int length = auxiliary.Length;
if (length == 1 && num[0] == '0')
{
// When number is zero
result = true;
}
else if (length > 1)
{
if ((length % 3) == 2)
{
// When length divide by 3 remainder is 2
// Mean need to add one more digit
auxiliary = "0" + auxiliary;
}
else if ((length % 3) == 1)
{
// Mean need to add two more digit
auxiliary = "00" + auxiliary;
}
// Get new length
length = auxiliary.Length;
for (int i = length - 1; i >= 0; --i)
{
temp = (auxiliary[i] - 48);
i--;
temp += (auxiliary[i] - 48) * 10;
i--;
temp += (auxiliary[i] - 48) * 100;
sum += (temp * sign);
sign = sign * -1;
}
if ((this.absValue(sum) % 13) == 0)
{
result = true;
}
}
if (result)
{
Console.WriteLine(" Given number (" +
num + ") is divisible by 13");
}
else
{
Console.WriteLine(" Given number (" +
num + ") is not divisible by 13");
}
}
public static void Main(String[] args)
{
// Test
}
}``````

#### Output

`````` Given number (45645645) is not divisible by 13
Given number (6576534533439) is divisible by 13
Given number (34965) is not divisible by 13
Given number (56456423434545645567567567867867) is not divisible by 13
Given number (9999912) is divisible by 13``````
``````package main
import "fmt"
// Go program for
// Check that if large number is divisible by 13
type Divisibility struct {}
func getDivisibility() * Divisibility {
var me *Divisibility = &Divisibility {}
return me
}
func (this Divisibility)absValue(x int) int {
if x < 0 {
return -x
}
return x
}
func(this Divisibility) isDivisibleBy13(num string) {
var result bool = false
var sum int = 0
var temp int = 0
var auxiliary string = num
var length int = len(auxiliary)
if length == 1 && num[0] == '0' {
// When number is zero
result = true
} else if length > 1 {
if (length % 3) == 2 {
// When length divide by 3 remainder is 2
// Mean need to add one more digit
auxiliary = "0" + auxiliary
} else if (length % 3) == 1 {
// Mean need to add two more digit
auxiliary = "00" + auxiliary
}
// Get new length
length = len(auxiliary)
for i := length - 1 ; i >= 0 ; i-- {
temp = (int(auxiliary[i]) - 48)
i--
temp += (int(auxiliary[i]) - 48) * 10
i--
temp += (int(auxiliary[i]) - 48) * 100
sum += (temp * sign)
sign = sign * -1
}
if (this.absValue(sum) % 13) == 0 {
result = true
}
}
if result {
fmt.Println(" Given number (", num, ") is divisible by 13")
} else {
fmt.Println(" Given number (", num, ") is not divisible by 13")
}
}
func main() {
var task * Divisibility = getDivisibility()
// Test
}``````

#### Output

`````` Given number (45645645) is not divisible by 13
Given number (6576534533439) is divisible by 13
Given number (34965) is not divisible by 13
Given number (56456423434545645567567567867867) is not divisible by 13
Given number (9999912) is divisible by 13``````
``````<?php
// Php program for
// Check that if large number is divisible by 13
class Divisibility
{
public	function absValue(\$x)
{
if (\$x < 0)
{
return -\$x;
}
return \$x;
}
public	function isDivisibleBy13(\$num)
{
\$result = false;
\$sum = 0;
\$sign = 1;
\$temp = 0;
\$auxiliary = \$num;
\$length = strlen(\$auxiliary);
if (\$length == 1 && \$num[0] == '0')
{
// When number is zero
\$result = true;
}
else if (\$length > 1)
{
if ((\$length % 3) == 2)
{
// When length divide by 3 remainder is 2
// Mean need to add one more digit
\$auxiliary = "0".\$auxiliary;
}
else if ((\$length % 3) == 1)
{
// Mean need to add two more digit
\$auxiliary = "00".\$auxiliary;
}
// Get new length
\$length = strlen(\$auxiliary);
for (\$i = \$length - 1; \$i >= 0; --\$i)
{
\$temp = (ord(\$auxiliary[\$i]) - 48);
\$i--;
\$temp += (ord(\$auxiliary[\$i]) - 48) * 10;
\$i--;
\$temp += (ord(\$auxiliary[\$i]) - 48) * 100;
\$sum += (\$temp * \$sign);
\$sign = \$sign * -1;
}
if ((\$this->absValue(\$sum) % 13) == 0)
{
\$result = true;
}
}
if (\$result)
{
echo(" Given number (".\$num.
") is divisible by 13".
"\n");
}
else
{
echo(" Given number (".\$num.
") is not divisible by 13".
"\n");
}
}
}

function main()
{
// Test
}
main();``````

#### Output

`````` Given number (45645645) is not divisible by 13
Given number (6576534533439) is divisible by 13
Given number (34965) is not divisible by 13
Given number (56456423434545645567567567867867) is not divisible by 13
Given number (9999912) is divisible by 13``````
``````// Node JS program for
// Check that if large number is divisible by 13
class Divisibility
{
absValue(x)
{
if (x < 0)
{
return -x;
}
return x;
}
isDivisibleBy13(num)
{
var result = false;
var sum = 0;
var sign = 1;
var temp = 0;
var auxiliary = num;
var length = auxiliary.length;
if (length == 1 && num.charAt(0) == '0')
{
// When number is zero
result = true;
}
else if (length > 1)
{
if ((length % 3) == 2)
{
// When length divide by 3 remainder is 2
// Mean need to add one more digit
auxiliary = "0" + auxiliary;
}
else if ((length % 3) == 1)
{
// Mean need to add two more digit
auxiliary = "00" + auxiliary;
}
// Get new length
length = auxiliary.length;
for (var i = length - 1; i >= 0; --i)
{
temp = (auxiliary.charAt(i).charCodeAt(0) - 48);
i--;
temp += (auxiliary.charAt(i).charCodeAt(0) - 48) * 10;
i--;
temp += (auxiliary.charAt(i).charCodeAt(0) - 48) * 100;
sum += (temp * sign);
sign = sign * -1;
}
if ((this.absValue(sum) % 13) == 0)
{
result = true;
}
}
if (result)
{
console.log(" Given number (" + num + ") is divisible by 13");
}
else
{
console.log(" Given number (" + num + ") is not divisible by 13");
}
}
}

function main()
{
// Test
}
main();``````

#### Output

`````` Given number (45645645) is not divisible by 13
Given number (6576534533439) is divisible by 13
Given number (34965) is not divisible by 13
Given number (56456423434545645567567567867867) is not divisible by 13
Given number (9999912) is divisible by 13``````
``````#  Python 3 program for
#  Check that if large number is divisible by 13
class Divisibility :
def absValue(self, x) :
if (x < 0) :
return -x

return x

def isDivisibleBy13(self, num) :
result = False
sum = 0
sign = 1
temp = 0
auxiliary = num
length = len(auxiliary)
if (length == 1 and num[0] == '0') :
#  When number is zero
result = True
elif (length > 1) :
if ((length % 3) == 2) :
#  When length divide by 3 remainder is 2
#  Mean need to add one more digit
auxiliary = "0" + auxiliary
elif ((length % 3) == 1) :
#  Mean need to add two more digit
auxiliary = "00" + auxiliary

#  Get new length
length = len(auxiliary)
i = length - 1
while (i >= 0) :
temp = (ord(auxiliary[i]) - 48)
i -= 1
temp += (ord(auxiliary[i]) - 48) * 10
i -= 1
temp += (ord(auxiliary[i]) - 48) * 100
sum += (temp * sign)
sign = sign * -1
i -= 1

if ((self.absValue(sum) % 13) == 0) :
result = True

if (result) :
print(" Given number (", num ,") is divisible by 13")
else :
print(" Given number (", num ,") is not divisible by 13")

def main() :
#  Test

if __name__ == "__main__": main()``````

#### Output

`````` Given number ( 45645645 ) is not divisible by 13
Given number ( 6576534533439 ) is divisible by 13
Given number ( 34965 ) is not divisible by 13
Given number ( 56456423434545645567567567867867 ) is not divisible by 13
Given number ( 9999912 ) is divisible by 13``````
``````#  Ruby program for
#  Check that if large number is divisible by 13
class Divisibility
def absValue(x)
if (x < 0)
return -x
end

return x
end

def isDivisibleBy13(num)
result = false
sum = 0
sign = 1
temp = 0
auxiliary = num
length = auxiliary.length
if (length == 1 && num[0] == '0')
#  When number is zero
result = true
elsif (length > 1)
if ((length % 3) == 2)
#  When length divide by 3 remainder is 2
#  Mean need to add one more digit
auxiliary = "0" + auxiliary
elsif ((length % 3) == 1)
#  Mean need to add two more digit
auxiliary = "00" + auxiliary
end

#  Get new length
length = auxiliary.length
i = length - 1
while (i >= 0)
temp = (auxiliary[i].ord - 48)
i -= 1
temp += (auxiliary[i].ord - 48) * 10
i -= 1
temp += (auxiliary[i].ord - 48) * 100
sum += (temp * sign)
sign = sign * -1
i -= 1
end

if ((self.absValue(sum) % 13) == 0)
result = true
end

end

if (result)
print(" Given number (", num ,") is divisible by 13\n")
else

print(" Given number (", num ,") is not divisible by 13\n")
end

end

end

def main()
#  Test
end

main()``````

#### Output

`````` Given number (45645645) is not divisible by 13
Given number (6576534533439) is divisible by 13
Given number (34965) is not divisible by 13
Given number (56456423434545645567567567867867) is not divisible by 13
Given number (9999912) is divisible by 13
``````
``````import scala.collection.mutable._;
// Scala program for
// Check that if large number is divisible by 13
class Divisibility()
{
def absValue(x: Int): Int = {
if (x < 0)
{
return -x;
}
return x;
}
def isDivisibleBy13(num: String): Unit = {
var result: Boolean = false;
var sum: Int = 0;
var sign: Int = 1;
var temp: Int = 0;
var auxiliary: String = num;
var length: Int = auxiliary.length();
if (length == 1 && num.charAt(0) == '0')
{
// When number is zero
result = true;
}
else if (length > 1)
{
if ((length % 3) == 2)
{
// When length divide by 3 remainder is 2
// Mean need to add one more digit
auxiliary = "0" + auxiliary;
}
else if ((length % 3) == 1)
{
// Mean need to add two more digit
auxiliary = "00" + auxiliary;
}
// Get new length
length = auxiliary.length();
var i: Int = length - 1;
while (i >= 0)
{
temp = (auxiliary.charAt(i).toInt - 48);
i -= 1;
temp += (auxiliary.charAt(i).toInt - 48) * 10;
i -= 1;
temp += (auxiliary.charAt(i).toInt - 48) * 100;
sum += (temp * sign);
sign = sign * -1;
i -= 1;
}
if ((absValue(sum) % 13) == 0)
{
result = true;
}
}
if (result)
{
println(" Given number (" + num + ") is divisible by 13");
}
else
{
println(" Given number (" + num + ") is not divisible by 13");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Divisibility = new Divisibility();
// Test
}
}``````

#### Output

`````` Given number (45645645) is not divisible by 13
Given number (6576534533439) is divisible by 13
Given number (34965) is not divisible by 13
Given number (56456423434545645567567567867867) is not divisible by 13
Given number (9999912) is divisible by 13``````
``````import Foundation;
// Swift 4 program for
// Check that if large number is divisible by 13
class Divisibility
{
func absValue(_ x: Int) -> Int
{
if (x < 0)
{
return -x;
}
return x;
}
func isDivisibleBy13(_ x: String)
{
let num = Array(x);
var result: Bool = false;
var sum: Int = 0;
var sign: Int = 1;
var temp: Int = 0;
var auxiliary: String = x;
var length: Int = auxiliary.count;
if (length == 1 && num[0] == "0")
{
// When number is zero
result = true;
}
else if (length > 1)
{
if ((length % 3) == 2)
{
// When length divide by 3 remainder is 2
// Mean need to add one more digit
auxiliary = "0" + auxiliary;
}
else if ((length % 3) == 1)
{
// Mean need to add two more digit
auxiliary = "00" + auxiliary;
}
// Get new length
length = auxiliary.count;
var i: Int = length - 1;
let v = Array(auxiliary);
while (i >= 0)
{
temp = (Int(UnicodeScalar(String(v[i]))!.value) - 48);
i -= 1;
temp += (Int(UnicodeScalar(String(v[i]))!.value) - 48) *
10;
i -= 1;
temp += (Int(UnicodeScalar(String(v[i]))!.value) - 48) *
100;
sum += (temp * sign);
sign = sign * -1;
i -= 1;
}
if ((self.absValue(sum) % 13) == 0)
{
result = true;
}
}
if (result)
{
print(" Given number (", x ,") is divisible by 13");
}
else
{
print(" Given number (", x ,") is not divisible by 13");
}
}
}
func main()
{
// Test
}
main();``````

#### Output

`````` Given number ( 45645645 ) is not divisible by 13
Given number ( 6576534533439 ) is divisible by 13
Given number ( 34965 ) is not divisible by 13
Given number ( 56456423434545645567567567867867 ) is not divisible by 13
Given number ( 9999912 ) is divisible by 13``````
``````// Kotlin program for
// Check that if large number is divisible by 13
class Divisibility
{
fun absValue(x: Int): Int
{
if (x < 0)
{
return -x;
}
return x;
}
fun isDivisibleBy13(num: String): Unit
{
var result: Boolean = false;
var sum: Int = 0;
var sign: Int = 1;
var temp: Int;
var auxiliary: String = num;
var length: Int = auxiliary.length;
if (length == 1 && num.get(0) == '0')
{
// When number is zero
result = true;
}
else if (length > 1)
{
if ((length % 3) == 2)
{
// When length divide by 3 remainder is 2
// Mean need to add one more digit
auxiliary = "0" + auxiliary;
}
else if ((length % 3) == 1)
{
// Mean need to add two more digit
auxiliary = "00" + auxiliary;
}
// Get new length
length = auxiliary.length;
var i: Int = length - 1;
while (i >= 0)
{
temp = (auxiliary.get(i).toInt() - 48);
i -= 1;
temp += (auxiliary.get(i).toInt() - 48) * 10;
i -= 1;
temp += (auxiliary.get(i).toInt() - 48) * 100;
sum += (temp * sign);
sign = sign * -1;
i -= 1;
}
if ((this.absValue(sum) % 13) == 0)
{
result = true;
}
}
if (result)
{
println(" Given number (" + num + ") is divisible by 13");
}
else
{
println(" Given number (" + num + ") is not divisible by 13");
}
}
}
fun main(args: Array < String > ): Unit
{
// Test
}``````

#### Output

`````` Given number (45645645) is not divisible by 13
Given number (6576534533439) is divisible by 13
Given number (34965) is not divisible by 13
Given number (56456423434545645567567567867867) is not divisible by 13
Given number (9999912) is divisible by 13``````

## Resultant Output Explanation

The given code has provided the output for various test cases. The output explains whether each given number is divisible by 13 or not. For example, in the output, the code states that the number "45645645" is not divisible by 13, while the number "6576534533439" is divisible by 13.

## Time Complexity

The time complexity of the code can be analyzed as follows:

1. The code checks the length of the number, which has a constant time complexity of O(1).
2. If the length is greater than 1, the code performs a loop from the end, extracting three digits at a time. This loop has a time complexity of O(n/3), where n is the length of the number.
3. Thus, the overall time complexity of the code is O(n/3).

## 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.

Categories
Relative Post