Skip to main content

Find digital root of a large number efficiently

The concept of the digital root of a number holds intrigue in the realm of mathematics and computer science. The digital root, also known as the repeated digital sum, is a single-digit value obtained by summing the digits of a number until only one digit remains. This article delves into an efficient method for calculating the digital root of a large number.

Problem Statement

Given a large number, the goal is to calculate its digital root—the smallest single-digit value derived by summing its digits until the sum itself becomes a single-digit number.

Example and Description

Consider the number 123456. The task is to calculate its digital root.

  • 1 + 2 + 3 + 4 + 5 + 6 = 21
  • 2 + 1 = 3

Thus, the digital root of 123456 is 3.

Idea to Solve

An efficient way to calculate the digital root involves a mathematical insight. The digital root of a number n is equal to 1 + ((n - 1) % 9). This formula drastically reduces the number of actual digit additions required.

Standard Pseudocode

function findDigitalRoot(num)
    sum = 0
    for i = 0 to length of num - 1
        sum = 1 + (sum + (num[i] - '0') - 1) % 9
    return sum

function digitalRoot(num)
    print "Given number:", num
    print "Digital root:", findDigitalRoot(num)

main
    task = new DigitSum()
    task.digitalRoot("123456")
    task.digitalRoot("123908756245134574732783343268")
end main

Algorithm Explanation

  1. Define the findDigitalRoot function that takes a string num as input. This function calculates the digital root using the formula 1 + ((num[i] - '0' - 1) % 9) and returns the result.
  2. In the digitalRoot function, display the given number and then call findDigitalRoot to calculate and display the digital root of the number.
  3. In the main function, create an instance of the DigitSum class.
  4. Call the digitalRoot function with the numbers "123456" and "123908756245134574732783343268".

Code Solution

/*
    Java Program
    Find digital root of a large number efficiently
*/
public class DigitSum
{
	// Find the digital root 
	public int findDigitalRoot(String num)
	{
		int sum = 0;
		// Sum of all digit
		for (int i = 0; i < num.length(); ++i)
		{
			sum = 1 + (sum + (num.charAt(i) - '0') - 1) % 9;
		}
		return 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 :
		    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
		    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (4 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (5 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (6 - '0') - 1 ) % 9 ) = 3
		    -------------------------------------
		    Result =  3
		*/
		task.digitalRoot("123456");
		/*
		Case B :
		Given number : 123908756245134574732783343268
		    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
		    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (9 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (0 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (8 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (7 - '0') - 1 ) % 9 ) = 3
		    ( 1 + ( 3 + (5 - '0') - 1 ) % 9 ) = 8
		    ( 1 + ( 8 + (6 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (4 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (5 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (1 - '0') - 1 ) % 9 ) = 8
		    ( 1 + ( 8 + (3 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (4 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (5 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (7 - '0') - 1 ) % 9 ) = 9
		    ( 1 + ( 9 + (4 - '0') - 1 ) % 9 ) = 4
		    ( 1 + ( 4 + (7 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (3 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (7 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (8 - '0') - 1 ) % 9 ) = 4
		    ( 1 + ( 4 + (3 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (3 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (4 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (3 - '0') - 1 ) % 9 ) = 8
		    ( 1 + ( 8 + (2 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (6 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (8 - '0') - 1 ) % 9 ) = 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
    Find digital root of a large number efficiently
*/

class DigitSum
{
	public:
		// Find the digital root
		int findDigitalRoot(string num)
		{
			int sum = 0;
			// Sum of all digit
			for (int i = 0; i < num.length(); ++i)
			{
				sum = 1 + (sum + (num[i] - '0') - 1) % 9;
			}
			return 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 :
	    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (4 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (5 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (6 - '0') - 1 ) % 9 ) = 3
	    -------------------------------------
	    Result =  3
	*/
	task->digitalRoot("123456");
	/*
	Case B :
	Given number : 123908756245134574732783343268
	    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (9 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (0 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (8 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (7 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (5 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (6 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (4 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (5 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (1 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (3 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (4 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (5 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (7 - '0') - 1 ) % 9 ) = 9
	    ( 1 + ( 9 + (4 - '0') - 1 ) % 9 ) = 4
	    ( 1 + ( 4 + (7 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (3 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (7 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (8 - '0') - 1 ) % 9 ) = 4
	    ( 1 + ( 4 + (3 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (3 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (4 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (3 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (2 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (6 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (8 - '0') - 1 ) % 9 ) = 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
    Find digital root of a large number efficiently
*/
public class DigitSum
{
	// Find the digital root
	public int findDigitalRoot(String num)
	{
		int sum = 0;
		// Sum of all digit
		for (int i = 0; i < num.Length; ++i)
		{
			sum = 1 + (sum + (num[i] - '0') - 1) % 9;
		}
		return 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 :
		    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
		    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (4 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (5 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (6 - '0') - 1 ) % 9 ) = 3
		    -------------------------------------
		    Result =  3
		*/
		task.digitalRoot("123456");
		/*
		Case B :
		Given number : 123908756245134574732783343268
		    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
		    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (9 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (0 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (8 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (7 - '0') - 1 ) % 9 ) = 3
		    ( 1 + ( 3 + (5 - '0') - 1 ) % 9 ) = 8
		    ( 1 + ( 8 + (6 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (4 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (5 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (1 - '0') - 1 ) % 9 ) = 8
		    ( 1 + ( 8 + (3 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (4 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (5 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (7 - '0') - 1 ) % 9 ) = 9
		    ( 1 + ( 9 + (4 - '0') - 1 ) % 9 ) = 4
		    ( 1 + ( 4 + (7 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (3 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (7 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (8 - '0') - 1 ) % 9 ) = 4
		    ( 1 + ( 4 + (3 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (3 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (4 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (3 - '0') - 1 ) % 9 ) = 8
		    ( 1 + ( 8 + (2 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (6 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (8 - '0') - 1 ) % 9 ) = 6
		    -------------------------------------
		    Result = 6
		*/
		task.digitalRoot("123908756245134574732783343268");
	}
}

input

 Given number : 123456
 Digital root : 3
 Given number : 123908756245134574732783343268
 Digital root : 6
<?php
/*
    Php Program
    Find digital root of a large number efficiently
*/
class DigitSum
{
	// Find the digital root
	public	function findDigitalRoot($num)
	{
		$sum = 0;
		// Sum of all digit
		for ($i = 0; $i < strlen($num); ++$i)
		{
			$sum = 1 + ($sum + (ord($num[$i]) - ord('0')) - 1) % 9;
		}
		return $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 :
	    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (4 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (5 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (6 - '0') - 1 ) % 9 ) = 3
	    -------------------------------------
	    Result =  3
	*/
	$task->digitalRoot("123456");
	/*
	Case B :
	Given number : 123908756245134574732783343268
	    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (9 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (0 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (8 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (7 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (5 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (6 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (4 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (5 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (1 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (3 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (4 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (5 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (7 - '0') - 1 ) % 9 ) = 9
	    ( 1 + ( 9 + (4 - '0') - 1 ) % 9 ) = 4
	    ( 1 + ( 4 + (7 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (3 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (7 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (8 - '0') - 1 ) % 9 ) = 4
	    ( 1 + ( 4 + (3 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (3 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (4 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (3 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (2 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (6 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (8 - '0') - 1 ) % 9 ) = 6
	    -------------------------------------
	    Result = 6
	*/
	$task->digitalRoot("123908756245134574732783343268");
}
main();

input

 Given number : 123456
 Digital root : 3
 Given number : 123908756245134574732783343268
 Digital root : 6
/*
    Node JS Program
    Find digital root of a large number efficiently
*/
class DigitSum
{
	// Find the digital root
	findDigitalRoot(num)
	{
		var sum = 0;
		// Sum of all digit
		for (var i = 0; i < num.length; ++i)
		{
			sum = 1 + (sum + (
              num.charAt(i).charCodeAt(0) - '0'.charCodeAt(0)) - 1) % 9;
		}
		return 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 :
	    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (4 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (5 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (6 - '0') - 1 ) % 9 ) = 3
	    -------------------------------------
	    Result =  3
	*/
	task.digitalRoot("123456");
	/*
	Case B :
	Given number : 123908756245134574732783343268
	    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (9 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (0 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (8 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (7 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (5 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (6 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (4 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (5 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (1 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (3 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (4 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (5 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (7 - '0') - 1 ) % 9 ) = 9
	    ( 1 + ( 9 + (4 - '0') - 1 ) % 9 ) = 4
	    ( 1 + ( 4 + (7 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (3 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (7 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (8 - '0') - 1 ) % 9 ) = 4
	    ( 1 + ( 4 + (3 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (3 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (4 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (3 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (2 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (6 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (8 - '0') - 1 ) % 9 ) = 6
	    -------------------------------------
	    Result = 6
	*/
	task.digitalRoot("123908756245134574732783343268");
}
main();

input

 Given number : 123456
 Digital root : 3
 Given number : 123908756245134574732783343268
 Digital root : 6
#    Python 3 Program
#    Find digital root of a large number efficiently
class DigitSum :
	#  Find the digital root
	def findDigitalRoot(self, num) :
		sum = 0
		#  Sum of all digit
		i = 0
		while (i < len(num)) :
			sum = 1 + (sum + (ord(num[i]) - ord('0')) - 1) % 9
			i += 1
		
		return 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 :
	#    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	#    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	#    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (4 - '0') - 1 ) % 9 ) = 1
	#    ( 1 + ( 1 + (5 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (6 - '0') - 1 ) % 9 ) = 3
	#    -------------------------------------
	#    Result =  3
	task.digitalRoot("123456")
	# Case B :
	# Given number : 123908756245134574732783343268
	#    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	#    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	#    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (9 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (0 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (8 - '0') - 1 ) % 9 ) = 5
	#    ( 1 + ( 5 + (7 - '0') - 1 ) % 9 ) = 3
	#    ( 1 + ( 3 + (5 - '0') - 1 ) % 9 ) = 8
	#    ( 1 + ( 8 + (6 - '0') - 1 ) % 9 ) = 5
	#    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	#    ( 1 + ( 7 + (4 - '0') - 1 ) % 9 ) = 2
	#    ( 1 + ( 2 + (5 - '0') - 1 ) % 9 ) = 7
	#    ( 1 + ( 7 + (1 - '0') - 1 ) % 9 ) = 8
	#    ( 1 + ( 8 + (3 - '0') - 1 ) % 9 ) = 2
	#    ( 1 + ( 2 + (4 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (5 - '0') - 1 ) % 9 ) = 2
	#    ( 1 + ( 2 + (7 - '0') - 1 ) % 9 ) = 9
	#    ( 1 + ( 9 + (4 - '0') - 1 ) % 9 ) = 4
	#    ( 1 + ( 4 + (7 - '0') - 1 ) % 9 ) = 2
	#    ( 1 + ( 2 + (3 - '0') - 1 ) % 9 ) = 5
	#    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	#    ( 1 + ( 7 + (7 - '0') - 1 ) % 9 ) = 5
	#    ( 1 + ( 5 + (8 - '0') - 1 ) % 9 ) = 4
	#    ( 1 + ( 4 + (3 - '0') - 1 ) % 9 ) = 7
	#    ( 1 + ( 7 + (3 - '0') - 1 ) % 9 ) = 1
	#    ( 1 + ( 1 + (4 - '0') - 1 ) % 9 ) = 5
	#    ( 1 + ( 5 + (3 - '0') - 1 ) % 9 ) = 8
	#    ( 1 + ( 8 + (2 - '0') - 1 ) % 9 ) = 1
	#    ( 1 + ( 1 + (6 - '0') - 1 ) % 9 ) = 7
	#    ( 1 + ( 7 + (8 - '0') - 1 ) % 9 ) = 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
#    Find digital root of a large number efficiently
class DigitSum 
	#  Find the digital root
	def findDigitalRoot(num) 
		sum = 0
		#  Sum of all digit
		i = 0
		while (i < num.length) 
			sum = 1 + (sum + (num[i].ord - '0'.ord) - 1) % 9
			i += 1
		end
		return sum
	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 :
	#    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	#    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	#    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (4 - '0') - 1 ) % 9 ) = 1
	#    ( 1 + ( 1 + (5 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (6 - '0') - 1 ) % 9 ) = 3
	#    -------------------------------------
	#    Result =  3
	task.digitalRoot("123456")
	# Case B :
	# Given number : 123908756245134574732783343268
	#    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	#    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	#    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (9 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (0 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (8 - '0') - 1 ) % 9 ) = 5
	#    ( 1 + ( 5 + (7 - '0') - 1 ) % 9 ) = 3
	#    ( 1 + ( 3 + (5 - '0') - 1 ) % 9 ) = 8
	#    ( 1 + ( 8 + (6 - '0') - 1 ) % 9 ) = 5
	#    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	#    ( 1 + ( 7 + (4 - '0') - 1 ) % 9 ) = 2
	#    ( 1 + ( 2 + (5 - '0') - 1 ) % 9 ) = 7
	#    ( 1 + ( 7 + (1 - '0') - 1 ) % 9 ) = 8
	#    ( 1 + ( 8 + (3 - '0') - 1 ) % 9 ) = 2
	#    ( 1 + ( 2 + (4 - '0') - 1 ) % 9 ) = 6
	#    ( 1 + ( 6 + (5 - '0') - 1 ) % 9 ) = 2
	#    ( 1 + ( 2 + (7 - '0') - 1 ) % 9 ) = 9
	#    ( 1 + ( 9 + (4 - '0') - 1 ) % 9 ) = 4
	#    ( 1 + ( 4 + (7 - '0') - 1 ) % 9 ) = 2
	#    ( 1 + ( 2 + (3 - '0') - 1 ) % 9 ) = 5
	#    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	#    ( 1 + ( 7 + (7 - '0') - 1 ) % 9 ) = 5
	#    ( 1 + ( 5 + (8 - '0') - 1 ) % 9 ) = 4
	#    ( 1 + ( 4 + (3 - '0') - 1 ) % 9 ) = 7
	#    ( 1 + ( 7 + (3 - '0') - 1 ) % 9 ) = 1
	#    ( 1 + ( 1 + (4 - '0') - 1 ) % 9 ) = 5
	#    ( 1 + ( 5 + (3 - '0') - 1 ) % 9 ) = 8
	#    ( 1 + ( 8 + (2 - '0') - 1 ) % 9 ) = 1
	#    ( 1 + ( 1 + (6 - '0') - 1 ) % 9 ) = 7
	#    ( 1 + ( 7 + (8 - '0') - 1 ) % 9 ) = 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
    Find digital root of a large number efficiently
*/
class DigitSum()
{
	// Find the digital root
	def findDigitalRoot(num: String): Int = {
		var sum: Int = 0;
		// Sum of all digit
		var i: Int = 0;
		while (i < num.length())
		{
			sum = 1 + (sum + (num.charAt(i).toInt - '0'.toInt) - 1) % 9;
			i += 1;
		}
		return sum;
	}
	// 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 :
		    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
		    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (4 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (5 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (6 - '0') - 1 ) % 9 ) = 3
		    -------------------------------------
		    Result =  3
		*/
		task.digitalRoot("123456");
		/*
		Case B :
		Given number : 123908756245134574732783343268
		    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
		    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (9 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (0 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (8 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (7 - '0') - 1 ) % 9 ) = 3
		    ( 1 + ( 3 + (5 - '0') - 1 ) % 9 ) = 8
		    ( 1 + ( 8 + (6 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (4 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (5 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (1 - '0') - 1 ) % 9 ) = 8
		    ( 1 + ( 8 + (3 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (4 - '0') - 1 ) % 9 ) = 6
		    ( 1 + ( 6 + (5 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (7 - '0') - 1 ) % 9 ) = 9
		    ( 1 + ( 9 + (4 - '0') - 1 ) % 9 ) = 4
		    ( 1 + ( 4 + (7 - '0') - 1 ) % 9 ) = 2
		    ( 1 + ( 2 + (3 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (7 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (8 - '0') - 1 ) % 9 ) = 4
		    ( 1 + ( 4 + (3 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (3 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (4 - '0') - 1 ) % 9 ) = 5
		    ( 1 + ( 5 + (3 - '0') - 1 ) % 9 ) = 8
		    ( 1 + ( 8 + (2 - '0') - 1 ) % 9 ) = 1
		    ( 1 + ( 1 + (6 - '0') - 1 ) % 9 ) = 7
		    ( 1 + ( 7 + (8 - '0') - 1 ) % 9 ) = 6
		    -------------------------------------
		    Result = 6
		*/
		task.digitalRoot("123908756245134574732783343268");
	}
}

input

 Given number : 123456
 Digital root : 3
 Given number : 123908756245134574732783343268
 Digital root : 6
import Foundation;
/*
    Swift 4 Program
    Find digital root of a large number efficiently
*/
class DigitSum
{
	// Find the digital root
	func findDigitalRoot(_ num: [Character]) -> Int
	{
		var sum = 0;
		// Sum of all digit
		var i = 0;
		while (i < num.count)
		{
			sum = 1 + (sum + 
                       (Int(UnicodeScalar(String(num[i]))!.value) 
                        - 
                        Int(UnicodeScalar(String("0"))!.value)) - 1) % 9;
			i += 1;
		}
		return 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(Array(num)));
	}
}
func main()
{
	let task = DigitSum();
	/*
	Case A :
	    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (4 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (5 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (6 - '0') - 1 ) % 9 ) = 3
	    -------------------------------------
	    Result =  3
	*/
	task.digitalRoot("123456");
	/*
	Case B :
	Given number : 123908756245134574732783343268
	    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (9 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (0 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (8 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (7 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (5 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (6 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (4 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (5 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (1 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (3 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (4 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (5 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (7 - '0') - 1 ) % 9 ) = 9
	    ( 1 + ( 9 + (4 - '0') - 1 ) % 9 ) = 4
	    ( 1 + ( 4 + (7 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (3 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (7 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (8 - '0') - 1 ) % 9 ) = 4
	    ( 1 + ( 4 + (3 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (3 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (4 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (3 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (2 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (6 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (8 - '0') - 1 ) % 9 ) = 6
	    -------------------------------------
	    Result = 6
	*/
	task.digitalRoot("123908756245134574732783343268");
}
main();

input

 Given number :  123456
 Digital root :  3
 Given number :  123908756245134574732783343268
 Digital root :  6
/*
    Kotlin Program
    Find digital root of a large number efficiently
*/
class DigitSum
{
	// Find the digital root
	fun findDigitalRoot(num: String): Int
	{
		var sum: Int = 0;
		// Sum of all digit
		var i: Int = 0;
		while (i < num.length)
		{
			sum = 1 + (sum + (num.get(i).toInt() - '0'.toInt()) - 1) % 9;
			i += 1;
		}
		return sum;
	}
	// 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 :
	    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (4 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (5 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (6 - '0') - 1 ) % 9 ) = 3
	    -------------------------------------
	    Result =  3
	*/
	task.digitalRoot("123456");
	/*
	Case B :
	Given number : 123908756245134574732783343268
	    ( 1 + ( 0 + (1 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (2 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (3 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (9 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (0 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (8 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (7 - '0') - 1 ) % 9 ) = 3
	    ( 1 + ( 3 + (5 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (6 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (4 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (5 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (1 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (3 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (4 - '0') - 1 ) % 9 ) = 6
	    ( 1 + ( 6 + (5 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (7 - '0') - 1 ) % 9 ) = 9
	    ( 1 + ( 9 + (4 - '0') - 1 ) % 9 ) = 4
	    ( 1 + ( 4 + (7 - '0') - 1 ) % 9 ) = 2
	    ( 1 + ( 2 + (3 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (2 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (7 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (8 - '0') - 1 ) % 9 ) = 4
	    ( 1 + ( 4 + (3 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (3 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (4 - '0') - 1 ) % 9 ) = 5
	    ( 1 + ( 5 + (3 - '0') - 1 ) % 9 ) = 8
	    ( 1 + ( 8 + (2 - '0') - 1 ) % 9 ) = 1
	    ( 1 + ( 1 + (6 - '0') - 1 ) % 9 ) = 7
	    ( 1 + ( 7 + (8 - '0') - 1 ) % 9 ) = 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 the digital root calculation is O(n), where 'n' is the number of digits in the input number. This is because the algorithm iterates through each digit once to calculate the sum and find the digital root.

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