Find digital root of a given number

An algorithm to find the digital root of a given number.

Everything is written in ES6.

Example

Input:
5674
493193

Output:
4 // 5 + 6 + 7 + 4 = 22 = 2 + 2 = 4
2 // 4 + 9 + 3 + 1 + 9 + 3 = 29 = 2 + 9 = 11 = 1 + 1 = 2

We are going to use to two different methods to solve this.

• Using a recursive method which will take O(n ^ 2). Where n is the no of digits.
• Using mathematical formula which will tak O(1) time.

Recursive method O(n ^ 2).

Implementation

• We will create a function that will calculate the sum of all the digits.
• If the sum becomes single digit then we will return it.
• Else we will call the same function to calculate the sum again.

let digitalRoot = (n) => {
  //calculate the sum of all the digits
  let sum = 0;
  while(parseInt(n) > 0){
    let temp = n % 10;
    sum = sum + temp;
    n = parseInt(n / 10);
  }
  
  //Check if the sum is single digit
  if(sum < 10){
    return sum;
  }
 
  //call the function again
  return digitalRoot(sum);
}

console.log(digitalRoot(257520643)); //7
console.log(digitalRoot(5674));      // 4
console.log(digitalRoot(493193));    // 2
console.log(digitalRoot(34758));     // 9

Time complexity: O(n ^ 2) where n is the no of digits.
Space complexity: O(n).

Time and Space complexity

• We are going to extract all the digits and sum them. After reducing if the number is not single digit then we repeat the step again. So it is n * (n - 1) * (n - 2) = O(n ^ 2) where n is the no of digits in the number.
• Our space complexity is determined by recursion depth. So suppose if the number is reducing by 1 digit in each then Space complexity is O(n) where n is the no of digits in the number.

Using mathematical method O(1).

Implementation

• We are going to subtract 1 from the number and then divide it by 9 and add 1 to its remainder.

let digitalRoot = (n) => {
 return (n - 1) % 9 + 1;
}

console.log(digitalRoot(257520643)); //7
console.log(digitalRoot(5674));      // 4
console.log(digitalRoot(493193));    // 2
console.log(digitalRoot(34758));     // 9

Time complexity: O(1).
Space complexity: O(1).

Time and Space complexity

• We are using just simple mathematical formula so Time complexity is O(1).
• We are not using any extra space so Space complexity is O(1).