Let's learn how to solve the Recursive Digit Sum challenge from the HackerRank website.

This problem is about finding the super digit of an integer. We first need to understand what is meant by a super digit. We are told that if an integer has only one digit, then that integer itself is the super digit. However, if that integer is comprised of multiple digits, then the super digit is equal to the sum of the digits.

For example, the super digit of 9875 is 2, and it is found by doing the following.

superDigit(9875) = 9+8+7+5 = 29 
superDigit(29) 	 = 2 + 9 = 11
superDigit(11)	 = 1 + 1 = 2
superDigit(2)		 = 2  

We are asked to define a superDigit(n, k) function that receives a string n and an integer k. The string n is a string representation of the integer that we are starting with. The integer k represents how many times we must concatenate the string n to itself before computing its super digit. The function should return the super digit as an integer.

For example, superDigit('9875', 4) should result in the following recursive result.

superDigit(9875987598759875) = (9+8+7+5)*4 = 116
superDigit(116) = 1+1+6 = 8
superDigit(8) = 8

The sum of the digits in 9875 concatenated to itself 4 times is 116. The digits in 116 have a sum of 8. Since 8 has a single digit, it is the super digit.

Pseudo code solution

1. If the length of string n is 1, return an integer representation of n.
2. Else, loop over each digit in string n.
   • Compute the sum of all digits in n.
   • Compute the multiplication of that sum by the integer k.
   • Return a recursive function call with a string representation of the final computed value as n, and 1 as k.

Code solution

function superDigit(n, k) {
  if (n.length === 1) {
    return parseInt(n);
  }

  let sum = 0;
  for (let i = 0; i < n.length; i++) {
    sum += parseInt(n[i]);
  }

  sum *= k;

  return superDigit(sum.toString(), 1);
}

Test cases

Let's test the superDigit function above. For the first test case, we will use '123' as n and 3 as k.

console.log(superDigit('123', 3)); // 9

Let's manually test it to see if 9 is indeed the super digit.

1+2+3 = 6
6*3   = 18
1+8   = 9

For the next test case, we will use '148' as n and 3 as k.

console.log(superDigit('148', 3)); // 3

Let's manually test it to see if 3 is indeed the super digit.

1+4+8 = 13
13*3  = 39
3+9   = 12
1+2   = 3

Time and space complexity

If n has only one digit, the Big O time complexity of the solution is constant, or O(1), because we simply return it from the function.

However, if n is comprised of more than one digit, then the Big O time complexity of the solution is O(log(n) + k(n)), where n is the numeric value of the input string and k(n) is the number of iterations until n has length of 1, ending the recursive cycle. The complexity O(log(n) + k(n)) can be written as just O(log(n)).

Why O(log n)? To make it more obvious, let's represent numbers in base 10 notation.

O(log(100)) = 2
O(log(1000)) = 3
O(log(10000)) = 4

For every digit that n grows by, the number of iterations required to compute its super digit also increases, represented by the logarithmic value of n.

The Big O space complexity of the solution is constant, or O(1). Regardless of the length of the string of digits, or the number of times to concatenate it to itself, we'll always require the same numeric sum variable to be stored in memory.

More resources

For more info on Big O notation for time complexity, consult this Big O Cheat Sheet from freeCodeCamp.