6. Find a Single Digit

Here's the problem presented by the interviewer:

Given a non-negative integernum, repeatedly add all of its digits until the result has only one digit.

For example:

Givennum = 38, the process is 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Define the Problem

The problem has been well defined by the interviewer, but let's further clarify.

Jonathan: Can I use JavaScript?

Interviewer: Sure.

Jonathan: I'm assuming the size of the non-negative integer can be as big as possible.

Interviewer: Yes.

---

Think

Jonathan thinks about the problem for a bit. This one has been a bit tricky, but he can already think of one way to solve. Here's his pseudocode:

/* Create function that will convert number to array, since array can be indexed and looped over and then
   converted back into an array of numbers */
// Use the function above as a helper function for execution function.
/* Execution function will take in the number as an argument and then check to see if the number is already
   a single digit. */
   // Call the number-to-array helper function to get an array of numbers to store in a variable.
// Create a function that will take in the array of numbers and return back a single digit.
   /* The function can be recursive, since it will need to keep running the sum of the digits until a single
   digit is found. */

This problem seems to be a bit complicated, so Jonathan thinks carefully about how he's going to implement the algorithm.

---

Write Code and Syntax

Now that the hard part is done, Jonathan just needs to write out the syntax to fill in the pseudocode. As Jonathan writes the code, he explains the syntax.

/* Create function that will convert number to array, since array can be indexed and looped over and then
   converted back into an array of numbers */

   function splitIntToArr(passedInt) {
      var arrString = passedInt.toString().split("");
      var arrNum = [];
      for (var i = 0; i < arrString.length; i++) {
    arrNum.push(parseInt(arrString[i]));
      }
      return arrNum;
   }

// Use the function above as a helper function for execution function.
/* Execution function will take in the number as an argument and then check to see if the number is already
   a single digit. */

   function userExecution(userNum) {
    if (userNum < 10) {
        return userNum;
    }
    return addElements(userNum);
   }

// Create a function that will take in the array of numbers and return back a single digit.
/* The function can be recursive, since it will need to keep running the sum of the digits until a single
   digit is found. */

    function addElements(passedNum) {
        var num = 0;
        var arr = splitIntToArr(passedNum);

        for (var i = 0; i < arr.length; i++) {
            num += arr[i];
        }

        if (num < 10) {
            return num;
        } else {
            return addElements(num);
        }
    }

Jonathan: This is a solution I came up with. I wanted to split up the number into digits, so I created a helper function that splits up the number into an array of numbers.

I then created a function that would form the entry point for the number argument. I put in a simple validation to return the number back if it's already a single digit. Then, I run the array helper function and pass the array of numbers to the recursive function.

The recursive function takes in an array of numbers, looping through each one to sum up the individual digits. If the sum of the digits is a single digit, then the number is returned. Otherwise, the number is split again into an array of numbers to be summed up until a single digit is retrieved.

Interviewer: Is this the most efficient method?

Jonathan studies his solution and thinks carefully.

Jonathan: I think I might have a simpler way to go about it.

function addElements(num) {
    var sum = 0;

    var str = num.toString();
    for(var i=0; i < str.length; i++){
        sum += parseInt(str.charAt(i));
    }

    if(sum < 10){
        return sum;
    }else{
        return addElements(sum);
    }
}

function userExecution(userNum) {
    if (userNum < 10) {
        return userNum;
    }
    return addElements(userNum);
}

Jonathan: I realized that I didn't need to convert the string to an array of numbers, since I can iterate through the string. Therefore, I took to the helper function and just did a type conversion on the string as I summed up the number.

Interviewer: This still looks a bit long. Is there a more efficient way than using recursion?

Jonathan thinks for some time, considering alternative approaches.

Jonathan: I think I might have a more math-based solution.

function addDigits(num) {
    if (num == 0) {
        return 0;
    } else if (num%9==0) {
        return 9;
    } else {
        return num%9;
    }
}

Jonathan: After reflecting on the problem a bit more, I realized that there was a pattern occurring. If I get the remainder after dividing any > 1 digit number, I find the single digit remaining to be the sum of the multiple-digit numbers at the end.

Interviewer: Good.