Check that if large number is divisible by 7
In this article, we will discuss a problem of determining whether a large number is divisible by 7. We will provide an explanation of the problem, present a suitable example, discuss the algorithm and pseudocode, and provide an explanation of the resultant output.
Introduction
The problem we are addressing is the divisibility of a large number by 7. Given a large number, we need to check if it is divisible by 7 or not. Divisibility is a fundamental concept in mathematics, and being able to determine whether a number is divisible by another number is useful in various scenarios, such as in number theory, modular arithmetic, and algorithmic problem-solving.
Problem Statement
Let's consider the problem statement in detail. We are given a large number, represented as a string of digits. Our task is to check whether this number is divisible by 7. If the number is divisible by 7, we will output a message indicating that it is divisible; otherwise, we will output a message indicating that it is not divisible.
To illustrate the problem, let's consider an example:
Number: 45645645 Result: Given number (45645645) is not divisible by 7
In this example, the given number is 45645645. After performing the necessary calculations, we determine that it is not divisible by 7.
Algorithm and Pseudocode
To solve this problem, we can follow the following algorithm:
- Initialize a boolean variable "result" as false.
- Initialize an integer variable "sum" as 0.
- Initialize an integer variable "sign" as 1.
- Initialize an integer variable "temp" as 0.
- Copy the input number into an auxiliary string variable.
- Get the length of the auxiliary string.
- Check if the length is 1 and the first character of the string is '0'. If true, set the "result" variable to true.
- Check if the length divided by 3 has a remainder of 2. If true, add a leading '0' to the auxiliary string.
- Check if the length divided by 3 has a remainder of 1. If true, add two leading '0's to the auxiliary string.
- Update the length variable to match the length of the new auxiliary string.
- Iterate through the auxiliary string from the last character:
- Extract three consecutive digits from the auxiliary string and convert them to an integer.
- Update the sum by adding the product of "temp" and "sign".
- Flip the sign by multiplying it by -1.
- Check if the sum is divisible by 7. If true, set the "result" variable to true.
- Print the result message based on the value of the "result" variable.
Here is the pseudocode representation of the algorithm:
function isDivisibleBy7(num):
result = false
sum = 0
sign = 1
temp = 0
auxiliary = num
length = length of auxiliary
if length == 1 and auxiliary[0] == '0':
result = true
if length % 3 == 2:
auxiliary = '0' + auxiliary
if length % 3 == 1:
auxiliary = '00' + auxiliary
length = length of auxiliary
for i = length - 1 to 0 (step -1):
temp = toInt(auxiliary[i]) * 100
i = i - 1
temp = temp + toInt(auxiliary[i]) * 10
i = i - 1
temp = temp + toInt(auxiliary[i])
sum = sum + temp * sign
sign = sign * -1
if sum % 7 == 0:
result = true
if result:
print("Given number (" + num + ") is divisible by 7")
else:
print("Given number (" + num + ") is not divisible by 7")
Code Solution
// Java program for
// Check that if large number is divisible by 7
public class Divisibility
{
public void isDivisibleBy7(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')
{
result = true;
}
else if (length > 0)
{
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 ((sum % 7) == 0)
{
result = true;
}
}
if (result)
{
System.out.println(" Given number (" +
num + ") is divisible by 7");
}
else
{
System.out.println(" Given number (" +
num + ") is not divisible by 7");
}
}
public static void main(String[] args)
{
Divisibility task = new Divisibility();
// Test
task.isDivisibleBy7("45645645");
task.isDivisibleBy7("65765345345");
task.isDivisibleBy7("34965");
task.isDivisibleBy7("56456423434545645567567567867867");
task.isDivisibleBy7("9999");
}
}
Output
Given number (45645645) is not divisible by 7
Given number (65765345345) is divisible by 7
Given number (34965) is divisible by 7
Given number (56456423434545645567567567867867) is divisible by 7
Given number (9999) is not divisible by 7
// Include header file
#include <iostream>
#include <string>
using namespace std;
// C++ program for
// Check that if large number is divisible by 7
class Divisibility
{
public: void isDivisibleBy7(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')
{
result = true;
}
else if (length > 0)
{
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 ((sum % 7) == 0)
{
result = true;
}
}
if (result)
{
cout << " Given number ("
<< num << ") is divisible by 7" << endl;
}
else
{
cout << " Given number ("
<< num << ") is not divisible by 7" << endl;
}
}
};
int main()
{
Divisibility *task = new Divisibility();
// Test
task->isDivisibleBy7("45645645");
task->isDivisibleBy7("65765345345");
task->isDivisibleBy7("34965");
task->isDivisibleBy7("56456423434545645567567567867867");
task->isDivisibleBy7("9999");
return 0;
}
Output
Given number (45645645) is not divisible by 7
Given number (65765345345) is divisible by 7
Given number (34965) is divisible by 7
Given number (56456423434545645567567567867867) is divisible by 7
Given number (9999) is not divisible by 7
// Include namespace system
using System;
// Csharp program for
// Check that if large number is divisible by 7
public class Divisibility
{
public void isDivisibleBy7(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')
{
result = true;
}
else if (length > 0)
{
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 ((sum % 7) == 0)
{
result = true;
}
}
if (result)
{
Console.WriteLine(" Given number (" + num + ") is divisible by 7");
}
else
{
Console.WriteLine(" Given number (" + num + ") is not divisible by 7");
}
}
public static void Main(String[] args)
{
Divisibility task = new Divisibility();
// Test
task.isDivisibleBy7("45645645");
task.isDivisibleBy7("65765345345");
task.isDivisibleBy7("34965");
task.isDivisibleBy7("56456423434545645567567567867867");
task.isDivisibleBy7("9999");
}
}
Output
Given number (45645645) is not divisible by 7
Given number (65765345345) is divisible by 7
Given number (34965) is divisible by 7
Given number (56456423434545645567567567867867) is divisible by 7
Given number (9999) is not divisible by 7
package main
import "fmt"
// Go program for
// Check that if large number is divisible by 7
func isDivisibleBy7(num string) {
var result bool = false
var sum int = 0
var sign int = 1
var temp int = 0
var auxiliary string = num
var length int = len(auxiliary)
if length == 1 && num[0] == '0' {
result = true
} else if length > 0 {
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 (sum % 7) == 0 {
result = true
}
}
if result {
fmt.Println(" Given number (", num, ") is divisible by 7")
} else {
fmt.Println(" Given number (", num, ") is not divisible by 7")
}
}
func main() {
// Test
isDivisibleBy7("45645645")
isDivisibleBy7("65765345345")
isDivisibleBy7("34965")
isDivisibleBy7("56456423434545645567567567867867")
isDivisibleBy7("9999")
}
Output
Given number (45645645) is not divisible by 7
Given number (65765345345) is divisible by 7
Given number (34965) is divisible by 7
Given number (56456423434545645567567567867867) is divisible by 7
Given number (9999) is not divisible by 7
<?php
// Php program for
// Check that if large number is divisible by 7
class Divisibility
{
public function isDivisibleBy7($num)
{
$result = false;
$sum = 0;
$sign = 1;
$temp = 0;
$auxiliary = $num;
$length = strlen($auxiliary);
if ($length == 1 && $num[0] == '0')
{
$result = true;
}
else if ($length > 0)
{
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 (($sum % 7) == 0)
{
$result = true;
}
}
if ($result)
{
echo(" Given number (".$num.
") is divisible by 7".
"\n");
}
else
{
echo(" Given number (".$num.
") is not divisible by 7".
"\n");
}
}
}
function main()
{
$task = new Divisibility();
// Test
$task->isDivisibleBy7("45645645");
$task->isDivisibleBy7("65765345345");
$task->isDivisibleBy7("34965");
$task->isDivisibleBy7("56456423434545645567567567867867");
$task->isDivisibleBy7("9999");
}
main();
Output
Given number (45645645) is not divisible by 7
Given number (65765345345) is divisible by 7
Given number (34965) is divisible by 7
Given number (56456423434545645567567567867867) is divisible by 7
Given number (9999) is not divisible by 7
// Node JS program for
// Check that if large number is divisible by 7
class Divisibility
{
isDivisibleBy7(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')
{
result = true;
}
else if (length > 0)
{
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.charCodeAt(i) - 48);
i--;
temp += (auxiliary.charCodeAt(i) - 48) * 10;
i--;
temp += (auxiliary.charCodeAt(i) - 48) * 100;
sum += (temp * sign);
sign = sign * -1;
}
if ((sum % 7) == 0)
{
result = true;
}
}
if (result)
{
console.log(" Given number (" + num + ") is divisible by 7");
}
else
{
console.log(" Given number (" + num + ") is not divisible by 7");
}
}
}
function main()
{
var task = new Divisibility();
// Test
task.isDivisibleBy7("45645645");
task.isDivisibleBy7("65765345345");
task.isDivisibleBy7("34965");
task.isDivisibleBy7("56456423434545645567567567867867");
task.isDivisibleBy7("9999");
}
main();
Output
Given number (45645645) is not divisible by 7
Given number (65765345345) is divisible by 7
Given number (34965) is divisible by 7
Given number (56456423434545645567567567867867) is divisible by 7
Given number (9999) is not divisible by 7
# Python 3 program for
# Check that if large number is divisible by 7
class Divisibility :
def isDivisibleBy7(self, num) :
result = False
sum = 0
sign = 1
temp = 0
auxiliary = num
length = len(auxiliary)
if (length == 1 and num[0] == '0') :
result = True
elif (length > 0) :
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 ((sum % 7) == 0) :
result = True
if (result) :
print(" Given number (", num ,") is divisible by 7")
else :
print(" Given number (", num ,") is not divisible by 7")
def main() :
task = Divisibility()
# Test
task.isDivisibleBy7("45645645")
task.isDivisibleBy7("65765345345")
task.isDivisibleBy7("34965")
task.isDivisibleBy7("56456423434545645567567567867867")
task.isDivisibleBy7("9999")
if __name__ == "__main__": main()
Output
Given number ( 45645645 ) is not divisible by 7
Given number ( 65765345345 ) is divisible by 7
Given number ( 34965 ) is divisible by 7
Given number ( 56456423434545645567567567867867 ) is divisible by 7
Given number ( 9999 ) is not divisible by 7
# Ruby program for
# Check that if large number is divisible by 7
class Divisibility
def isDivisibleBy7(num)
result = false
sum = 0
sign = 1
temp = 0
auxiliary = num
length = auxiliary.length
if (length == 1 && num[0] == '0')
result = true
elsif (length > 0)
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 ((sum % 7) == 0)
result = true
end
end
if (result)
print(" Given number (",
num ,") is divisible by 7", "\n")
else
print(" Given number (",
num ,") is not divisible by 7", "\n")
end
end
end
def main()
task = Divisibility.new()
# Test
task.isDivisibleBy7("45645645")
task.isDivisibleBy7("65765345345")
task.isDivisibleBy7("34965")
task.isDivisibleBy7("56456423434545645567567567867867")
task.isDivisibleBy7("9999")
end
main()
Output
Given number (45645645) is not divisible by 7
Given number (65765345345) is divisible by 7
Given number (34965) is divisible by 7
Given number (56456423434545645567567567867867) is divisible by 7
Given number (9999) is not divisible by 7
import scala.collection.mutable._;
// Scala program for
// Check that if large number is divisible by 7
class Divisibility()
{
def isDivisibleBy7(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')
{
result = true;
}
else if (length > 0)
{
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 ((sum % 7) == 0)
{
result = true;
}
}
if (result)
{
println(" Given number (" + num + ") is divisible by 7");
}
else
{
println(" Given number (" + num + ") is not divisible by 7");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Divisibility = new Divisibility();
// Test
task.isDivisibleBy7("45645645");
task.isDivisibleBy7("65765345345");
task.isDivisibleBy7("34965");
task.isDivisibleBy7("56456423434545645567567567867867");
task.isDivisibleBy7("9999");
}
}
Output
Given number (45645645) is not divisible by 7
Given number (65765345345) is divisible by 7
Given number (34965) is divisible by 7
Given number (56456423434545645567567567867867) is divisible by 7
Given number (9999) is not divisible by 7
import Foundation;
// Swift 4 program for
// Check that if large number is divisible by 7
class Divisibility
{
func isDivisibleBy7(_ num: String)
{
var result: Bool = false;
var sum: Int = 0;
var sign: Int = 1;
var temp: Int = 0;
var auxiliary: String = num;
var length: Int = auxiliary.count;
if (length == 1 && Array(num)[0] == "0")
{
result = true;
}
else if (length > 0)
{
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;
let v = Array(auxiliary);
var i: Int = length - 1;
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 ((sum % 7) == 0)
{
result = true;
}
}
if (result)
{
print(" Given number (", num ,") is divisible by 7");
}
else
{
print(" Given number (", num ,") is not divisible by 7");
}
}
}
func main()
{
let task: Divisibility = Divisibility();
// Test
task.isDivisibleBy7("45645645");
task.isDivisibleBy7("65765345345");
task.isDivisibleBy7("34965");
task.isDivisibleBy7("56456423434545645567567567867867");
task.isDivisibleBy7("9999");
}
main();
Output
Given number ( 45645645 ) is not divisible by 7
Given number ( 65765345345 ) is divisible by 7
Given number ( 34965 ) is divisible by 7
Given number ( 56456423434545645567567567867867 ) is divisible by 7
Given number ( 9999 ) is not divisible by 7
// Kotlin program for
// Check that if large number is divisible by 7
class Divisibility
{
fun isDivisibleBy7(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')
{
result = true;
}
else if (length > 0)
{
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 ((sum % 7) == 0)
{
result = true;
}
}
if (result)
{
println(" Given number (" + num + ") is divisible by 7");
}
else
{
println(" Given number (" + num + ") is not divisible by 7");
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Divisibility = Divisibility();
// Test
task.isDivisibleBy7("45645645");
task.isDivisibleBy7("65765345345");
task.isDivisibleBy7("34965");
task.isDivisibleBy7("56456423434545645567567567867867");
task.isDivisibleBy7("9999");
}
Output
Given number (45645645) is not divisible by 7
Given number (65765345345) is divisible by 7
Given number (34965) is divisible by 7
Given number (56456423434545645567567567867867) is divisible by 7
Given number (9999) is not divisible by 7
Resultant Output Explanation
Now, let's analyze the output obtained from running the given code:
Given number (45645645) is not divisible by 7 Given number (65765345345) is divisible by 7 Given number (34965) is divisible by 7 Given number (56456423434545645567567567867867) is divisible by 7 Given number (9999) is not divisible by 7
The code executes the "isDivisibleBy7" method for various input numbers and prints the corresponding result messages. Each message indicates whether the given number is divisible by 7 or not.
Time Complexity
The time complexity of the provided code can be analyzed as follows:
- Copying the input number into the auxiliary string takes O(N) time, where N is the length of the input number.
- The subsequent operations involve iterating over the digits of the auxiliary string, which also takes O(N) time.
- Overall, the time complexity of the code is O(N), where N is the length of the input number.
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