Digital root of a large number using recursion
The digital root of a number is the sum of its digits until a single-digit number is obtained. For example, the digital root of 123 is 1 + 2 + 3 = 6, and the digital root of 456 is 4 + 5 + 6 = 15, which further becomes 1 + 5 = 6. In this article, we will discuss how to find the digital root of a large number using a recursive approach.
Problem Statement
Given a large number represented as a string, we need to find its digital root using recursion.
Example
Consider the number "123456." The digital root is calculated as follows: 1 + 2 + 3 + 4 + 5 + 6 = 21 2 + 1 = 3 Hence, the digital root of 123456 is 3.
Pseudocode
function findDigitalRoot(num):
if length(num) == 1:
return num
sum = 0
for i = 0 to length(num)-1:
sum += num[i] - '0'
return findDigitalRoot(convertToString(sum))
function digitalRoot(num):
print("Given number : " + num)
print("Digital root : " + findDigitalRoot(num))
Algorithm
The algorithm to find the digital root of a number using recursion can be described as follows:
- Define a function findDigitalRoot(num) that takes a string num as input.
- If the length of num is 1, return the number as the digital root.
- Initialize a variable sum to store the sum of digits.
- Iterate through each character in num, convert it to an integer, and add it to the sum.
- Recursively call findDigitalRoot() with the sum as the new input.
- Repeat steps 2 to 5 until the digital root is obtained.
- Finally, the digital root will be a single-digit number, and we return it.
Explanation:
- The
findDigitalRoot
function is a recursive function that calculates the digital root of the input numbernum
. - If the length of
num
is 1, it means we have a single-digit number, and we return the number as the digital root. - Otherwise, we initialize a variable
sum
to store the sum of digits and loop through each digit in the string representation of the number. - We convert each character to an integer by subtracting the ASCII value of '0' from the character. This gives us the actual digit value.
- We add all the digits and recursively call the
findDigitalRoot
function with the new sum. - The process repeats until we obtain a single-digit digital root, and we return it.
Program Solution
/*
Java Program
Digital root of a large number using recursion
*/
public class DigitSum
{
// Find the digital root using recursion process
public String findDigitalRoot(String num)
{
if (num.length() == 1)
{
// Returning the result of single digit
return num;
}
int sum = 0;
// Sum of all digit
for (int i = 0; i < num.length(); ++i)
{
sum += num.charAt(i) - '0';
}
return findDigitalRoot("" + sum);
}
// Handles the request to find digital root of given string number
public void digitalRoot(String num)
{
// Display given number
System.out.println(" Given number : " + num);
// Display calculated result
System.out.println(" Digital root : " + findDigitalRoot(num));
}
public static void main(String[] args)
{
DigitSum task = new DigitSum();
/*
Case A :
Given number : 123456
1 + 2 + 3 + 4 + 5 + 6 = 21
2 + 1 = 3
Result = 3
*/
task.digitalRoot("123456");
/*
Case B :
Given number : 123908756245134574732783343268
1 + 2 + 3 + 9 + 0 + 8 + 7 + 5 + 6
+ 2 + 4 + 5 + 1 + 3 + 4
+ 5 + 7 + 4 + 7 + 3 + 2 + 7
+ 8 + 3 + 3 + 4 + 3 + 2 + 6 + 8 = 132
1 + 3 + 2 = 6
Result = 6
*/
task.digitalRoot("123908756245134574732783343268");
}
}
input
Given number : 123456
Digital root : 3
Given number : 123908756245134574732783343268
Digital root : 6
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ Program
Digital root of a large number using recursion
*/
class DigitSum
{
public:
// Find the digital root using recursion process
string findDigitalRoot(string num)
{
if (num.length() == 1)
{
// Returning the result of single digit
return num;
}
int sum = 0;
// Sum of all digit
for (int i = 0; i < num.length(); ++i)
{
sum += num[i] - '0';
}
return this->findDigitalRoot(to_string(sum));
}
// Handles the request to find digital root of given string number
void digitalRoot(string num)
{
// Display given number
cout << " Given number : " << num << endl;
// Display calculated result
cout << " Digital root : " << this->findDigitalRoot(num) << endl;
}
};
int main()
{
DigitSum *task = new DigitSum();
/*
Case A :
Given number : 123456
1 + 2 + 3 + 4 + 5 + 6 = 21
2 + 1 = 3
Result = 3
*/
task->digitalRoot("123456");
/*
Case B :
Given number : 123908756245134574732783343268
1 + 2 + 3 + 9 + 0 + 8 + 7 + 5 + 6
+ 2 + 4 + 5 + 1 + 3 + 4
+ 5 + 7 + 4 + 7 + 3 + 2 + 7
+ 8 + 3 + 3 + 4 + 3 + 2 + 6 + 8 = 132
1 + 3 + 2 = 6
Result = 6
*/
task->digitalRoot("123908756245134574732783343268");
return 0;
}
input
Given number : 123456
Digital root : 3
Given number : 123908756245134574732783343268
Digital root : 6
// Include namespace system
using System;
/*
Csharp Program
Digital root of a large number using recursion
*/
public class DigitSum
{
// Find the digital root using recursion process
public String findDigitalRoot(String num)
{
if (num.Length == 1)
{
// Returning the result of single digit
return num;
}
int sum = 0;
// Sum of all digit
for (int i = 0; i < num.Length; ++i)
{
sum += num[i] - '0';
}
return this.findDigitalRoot("" + sum);
}
// Handles the request to find digital root of given string number
public void digitalRoot(String num)
{
// Display given number
Console.WriteLine(" Given number : " + num);
// Display calculated result
Console.WriteLine(" Digital root : " + this.findDigitalRoot(num));
}
public static void Main(String[] args)
{
DigitSum task = new DigitSum();
/*
Case A :
Given number : 123456
1 + 2 + 3 + 4 + 5 + 6 = 21
2 + 1 = 3
Result = 3
*/
task.digitalRoot("123456");
/*
Case B :
Given number : 123908756245134574732783343268
1 + 2 + 3 + 9 + 0 + 8 + 7 + 5 + 6
+ 2 + 4 + 5 + 1 + 3 + 4
+ 5 + 7 + 4 + 7 + 3 + 2 + 7
+ 8 + 3 + 3 + 4 + 3 + 2 + 6 + 8 = 132
1 + 3 + 2 = 6
Result = 6
*/
task.digitalRoot("123908756245134574732783343268");
}
}
input
Given number : 123456
Digital root : 3
Given number : 123908756245134574732783343268
Digital root : 6
<?php
/*
Php Program
Digital root of a large number using recursion
*/
class DigitSum
{
// Find the digital root using recursion process
public function findDigitalRoot($num)
{
if (strlen($num) == 1)
{
// Returning the result of single digit
return $num;
}
$sum = 0;
// Sum of all digit
for ($i = 0; $i < strlen($num); ++$i)
{
$sum += ord($num[$i]) - ord('0');
}
return $this->findDigitalRoot(strval($sum));
}
// Handles the request to find digital root of given string number
public function digitalRoot($num)
{
// Display given number
echo (" Given number : ".$num."\n");
// Display calculated result
echo (" Digital root : ".$this->findDigitalRoot($num)."\n");
}
}
function main()
{
$task = new DigitSum();
/*
Case A :
Given number : 123456
1 + 2 + 3 + 4 + 5 + 6 = 21
2 + 1 = 3
Result = 3
*/
$task->digitalRoot("123456");
/*
Case B :
Given number : 123908756245134574732783343268
1 + 2 + 3 + 9 + 0 + 8 + 7 + 5 + 6
+ 2 + 4 + 5 + 1 + 3 + 4
+ 5 + 7 + 4 + 7 + 3 + 2 + 7
+ 8 + 3 + 3 + 4 + 3 + 2 + 6 + 8 = 132
1 + 3 + 2 = 6
Result = 6
*/
$task->digitalRoot("123908756245134574732783343268");
}
main();
input
Given number : 123456
Digital root : 3
Given number : 123908756245134574732783343268
Digital root : 6
/*
Node JS Program
Digital root of a large number using recursion
*/
class DigitSum
{
// Find the digital root using recursion process
findDigitalRoot(num)
{
if (num.length == 1)
{
// Returning the result of single digit
return num;
}
var sum = 0;
// Sum of all digit
for (var i = 0; i < num.length; ++i)
{
sum += num.charAt(i).charCodeAt(0) - '0'.charCodeAt(0);
}
return this.findDigitalRoot("" + sum);
}
// Handles the request to find digital root of given string number
digitalRoot(num)
{
// Display given number
console.log(" Given number : " + num);
// Display calculated result
console.log(" Digital root : " + this.findDigitalRoot(num));
}
}
function main()
{
var task = new DigitSum();
/*
Case A :
Given number : 123456
1 + 2 + 3 + 4 + 5 + 6 = 21
2 + 1 = 3
Result = 3
*/
task.digitalRoot("123456");
/*
Case B :
Given number : 123908756245134574732783343268
1 + 2 + 3 + 9 + 0 + 8 + 7 + 5 + 6
+ 2 + 4 + 5 + 1 + 3 + 4
+ 5 + 7 + 4 + 7 + 3 + 2 + 7
+ 8 + 3 + 3 + 4 + 3 + 2 + 6 + 8 = 132
1 + 3 + 2 = 6
Result = 6
*/
task.digitalRoot("123908756245134574732783343268");
}
main();
input
Given number : 123456
Digital root : 3
Given number : 123908756245134574732783343268
Digital root : 6
# Python 3 Program
# Digital root of a large number using recursion
class DigitSum :
# Find the digital root using recursion process
def findDigitalRoot(self, num) :
if (len(num) == 1) :
# Returning the result of single digit
return num
sum = 0
# Sum of all digit
i = 0
while (i < len(num)) :
sum += ord(num[i]) - ord('0')
i += 1
return self.findDigitalRoot(str(sum))
# Handles the request to find digital root of given string number
def digitalRoot(self, num) :
# Display given number
print(" Given number : ", num)
# Display calculated result
print(" Digital root : ", self.findDigitalRoot(num))
def main() :
task = DigitSum()
# Case A :
# Given number : 123456
# 1 + 2 + 3 + 4 + 5 + 6 = 21
# 2 + 1 = 3
# Result = 3
task.digitalRoot("123456")
# Case B :
# Given number : 123908756245134574732783343268
# 1 + 2 + 3 + 9 + 0 + 8 + 7 + 5 + 6
# + 2 + 4 + 5 + 1 + 3 + 4
# + 5 + 7 + 4 + 7 + 3 + 2 + 7
# + 8 + 3 + 3 + 4 + 3 + 2 + 6 + 8 = 132
# 1 + 3 + 2 = 6
# Result = 6
task.digitalRoot("123908756245134574732783343268")
if __name__ == "__main__": main()
input
Given number : 123456
Digital root : 3
Given number : 123908756245134574732783343268
Digital root : 6
# Ruby Program
# Digital root of a large number using recursion
class DigitSum
# Find the digital root using recursion process
def findDigitalRoot(num)
if (num.length == 1)
# Returning the result of single digit
return num
end
sum = 0
# Sum of all digit
i = 0
while (i < num.length)
sum += num[i].ord - '0'.ord
i += 1
end
return self.findDigitalRoot(sum.to_s)
end
# Handles the request to find digital root of given string number
def digitalRoot(num)
# Display given number
print(" Given number : ", num, "\n")
# Display calculated result
print(" Digital root : ", self.findDigitalRoot(num), "\n")
end
end
def main()
task = DigitSum.new()
# Case A :
# Given number : 123456
# 1 + 2 + 3 + 4 + 5 + 6 = 21
# 2 + 1 = 3
# Result = 3
task.digitalRoot("123456")
# Case B :
# Given number : 123908756245134574732783343268
# 1 + 2 + 3 + 9 + 0 + 8 + 7 + 5 + 6
# + 2 + 4 + 5 + 1 + 3 + 4
# + 5 + 7 + 4 + 7 + 3 + 2 + 7
# + 8 + 3 + 3 + 4 + 3 + 2 + 6 + 8 = 132
# 1 + 3 + 2 = 6
# Result = 6
task.digitalRoot("123908756245134574732783343268")
end
main()
input
Given number : 123456
Digital root : 3
Given number : 123908756245134574732783343268
Digital root : 6
import scala.collection.mutable._;
/*
Scala Program
Digital root of a large number using recursion
*/
class DigitSum()
{
// Find the digital root using recursion process
def findDigitalRoot(num: String): String = {
if (num.length() == 1)
{
// Returning the result of single digit
return num;
}
var sum: Int = 0;
// Sum of all digit
var i: Int = 0;
while (i < num.length())
{
sum += num.charAt(i).toInt - '0'.toInt;
i += 1;
}
return findDigitalRoot( sum.toString());
}
// Handles the request to find digital root of given string number
def digitalRoot(num: String): Unit = {
// Display given number
println(" Given number : " + num);
// Display calculated result
println(" Digital root : " + findDigitalRoot(num));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: DigitSum = new DigitSum();
/*
Case A :
Given number : 123456
1 + 2 + 3 + 4 + 5 + 6 = 21
2 + 1 = 3
Result = 3
*/
task.digitalRoot("123456");
/*
Case B :
Given number : 123908756245134574732783343268
1 + 2 + 3 + 9 + 0 + 8 + 7 + 5 + 6
+ 2 + 4 + 5 + 1 + 3 + 4
+ 5 + 7 + 4 + 7 + 3 + 2 + 7
+ 8 + 3 + 3 + 4 + 3 + 2 + 6 + 8 = 132
1 + 3 + 2 = 6
Result = 6
*/
task.digitalRoot("123908756245134574732783343268");
}
}
input
Given number : 123456
Digital root : 3
Given number : 123908756245134574732783343268
Digital root : 6
import Foundation;
/*
Swift 4 Program
Digital root of a large number using recursion
*/
class DigitSum
{
// Find the digital root using recursion process
func findDigitalRoot(_ n: String) -> String
{
if (n.count == 1)
{
// Returning the result of single digit
return n;
}
let num = Array(n);
var sum = 0;
// Sum of all digit
var i = 0;
while (i < num.count)
{
sum += Int(UnicodeScalar(String(num[i]))!.value)
- Int(UnicodeScalar(String("0"))!.value);
i += 1;
}
return self.findDigitalRoot(""
+ String(sum));
}
// Handles the request to find digital root of given string number
func digitalRoot(_ num: String)
{
// Display given number
print(" Given number : ", num);
// Display calculated result
print(" Digital root : ", self.findDigitalRoot(num));
}
}
func main()
{
let task = DigitSum();
/*
Case A :
Given number : 123456
1 + 2 + 3 + 4 + 5 + 6 = 21
2 + 1 = 3
Result = 3
*/
task.digitalRoot("123456");
/*
Case B :
Given number : 123908756245134574732783343268
1 + 2 + 3 + 9 + 0 + 8 + 7 + 5 + 6
+ 2 + 4 + 5 + 1 + 3 + 4
+ 5 + 7 + 4 + 7 + 3 + 2 + 7
+ 8 + 3 + 3 + 4 + 3 + 2 + 6 + 8 = 132
1 + 3 + 2 = 6
Result = 6
*/
task.digitalRoot("123908756245134574732783343268");
}
main();
input
Given number : 123456
Digital root : 3
Given number : 123908756245134574732783343268
Digital root : 6
/*
Kotlin Program
Digital root of a large number using recursion
*/
class DigitSum
{
// Find the digital root using recursion process
fun findDigitalRoot(num: String): String
{
if (num.length == 1)
{
// Returning the result of single digit
return num;
}
var sum: Int = 0;
// Sum of all digit
var i: Int = 0;
while (i < num.length)
{
sum += num.get(i).toInt() - '0'.toInt();
i += 1;
}
return this.findDigitalRoot(sum.toString());
}
// Handles the request to find digital root of given string number
fun digitalRoot(num: String): Unit
{
// Display given number
println(" Given number : " + num);
// Display calculated result
println(" Digital root : " + this.findDigitalRoot(num));
}
}
fun main(args: Array < String > ): Unit
{
val task: DigitSum = DigitSum();
/*
Case A :
Given number : 123456
1 + 2 + 3 + 4 + 5 + 6 = 21
2 + 1 = 3
Result = 3
*/
task.digitalRoot("123456");
/*
Case B :
Given number : 123908756245134574732783343268
1 + 2 + 3 + 9 + 0 + 8 + 7 + 5 + 6
+ 2 + 4 + 5 + 1 + 3 + 4
+ 5 + 7 + 4 + 7 + 3 + 2 + 7
+ 8 + 3 + 3 + 4 + 3 + 2 + 6 + 8 = 132
1 + 3 + 2 = 6
Result = 6
*/
task.digitalRoot("123908756245134574732783343268");
}
input
Given number : 123456
Digital root : 3
Given number : 123908756245134574732783343268
Digital root : 6
Time Complexity
The time complexity of this algorithm is O(k), where k is the number of digits in the input number. Since we sum up all the digits in each recursive call until we obtain a single-digit number, the time complexity is linear with respect to the number of digits in the input.
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