Skip to main content

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:

  1. Define a function findDigitalRoot(num) that takes a string num as input.
  2. If the length of num is 1, return the number as the digital root.
  3. Initialize a variable sum to store the sum of digits.
  4. Iterate through each character in num, convert it to an integer, and add it to the sum.
  5. Recursively call findDigitalRoot() with the sum as the new input.
  6. Repeat steps 2 to 5 until the digital root is obtained.
  7. Finally, the digital root will be a single-digit number, and we return it.

Explanation:

  1. The findDigitalRoot function is a recursive function that calculates the digital root of the input number num.
  2. If the length of num is 1, it means we have a single-digit number, and we return the number as the digital root.
  3. Otherwise, we initialize a variable sum to store the sum of digits and loop through each digit in the string representation of the number.
  4. We convert each character to an integer by subtracting the ASCII value of '0' from the character. This gives us the actual digit value.
  5. We add all the digits and recursively call the findDigitalRoot function with the new sum.
  6. 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.

Last updated on by Kalkicode




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