Recursive Digit Sum

Yesterday afternoon the technician for a company that cleans ducts showed up for our appointment. Our dryer was having issues with the exhaust duct. We had to clean the dryer filter and restart the unit over a dozen times per load.

The technician arrived half hour earlier. I showed him the location for the exhaust and the dryer. He brought in some type of industrial vacuum and some hoses. I believe he used a camera to watch the operation while vacuuming the duct.

At some point he had to open the duct around the exhaust point. The exhaust duct has an end grid. Some type of insect had nested in the duct. He was able to clear the issue.

The technician drove a van. It had a large compressor in the bed. Not sure if it was powered by electricity or a generator. I wish I had the time to watch the entire cleaning operation. All was said and done in over an hour.

My wife started a wash. When done she move the load to the dryer. The drier failed a couple times. I took a look at the filter. It had collected some stuff that was blocking part of the exhaust flow. I cleared the filter with hot running water in the kitchen sink. After placing the filter back into the dryer all worked without issues.

We are very satisfied with the work done. If you live The Twin Cities area of Minneapolis and St. Paul and need the ducts in your home cleaned, I will gladly pass on the information.

Lately I have been solving LeetCode problems. I will continue to do so. That said I received a message from HackerRank suggesting the Recursive Digit Sum. If interested please take a look at the requirements and decide if you want to give it a try. As usual, spend some time attempting to solve it and if you run into issues or just need some ideas, come back and continue reading.

I decided to solve the problem using Java. I used the VSCode IDE and a Windows 10 computer. I prefer to solve problems using the tools I have installed and are using on my machine.

The description of the problem follows:

Complete the function superDigit in the editor below.
It must return the calculated super digit as an integer.

superDigit has the following parameter(s):

n: a string representation of an integer
k: an integer, the times to concatenate  to make

Input Format

The first line contains two space separated integers, n and k.

Constraints
	o 1 <= n < 10^100000
	o 1 <= k <= 10^5

In my opinion, reading the requirements leave out some information.

For example, the super digit of 9875 will be calculated as:

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

This last example illustrates what is required.

We are given a string of digits. We are also given a number ‘k’ that specifies how many copies of the string must be concatenated to get to the initial sting named ‘n’. The example illustrates processing for a string without multiplier. If specified, the multiplier would be 1.

If we add all the digits in the string ‘9785’ we get 29. Since 29 has two digits we need to repeat the process.  The second time we get 11 which still holds two digits. The third time we apply the process our result is equal to 2. Since this is a single digit, we have found the super digit. Make sure you get the objective of the processing.

Now we can think of possible optimizations. If we have the same string concatenated multiple times as indicated by ‘k’, we can add the original digits multiplied by 4.

    // Complete the superDigit function below.
    static int superDigit(String n, int k) {
	
    }

We need to implement the superDigit() function to solve the problem.

148 3

main <<< n ==>148<== k: 3
main <<< superDigit0: 3
main <<<  superDigit: 3


9875 1

main <<< n ==>9875<== k: 1
main <<< superDigit0: 2
main <<<  superDigit: 2


9875 4

main <<< n ==>9875<== k: 4
main <<< superDigit0: 8
main <<<  superDigit: 8


123 3

main <<< n ==>123<== k: 3
main <<< superDigit0: 9
main <<<  superDigit: 9


123 1

main <<< n ==>123<== k: 1
main <<< superDigit0: 6
main <<<  superDigit: 6


1234 1

main <<< n ==>1234<== k: 1
main <<< superDigit0: 1
main <<<  superDigit: 1


1234567890 100000

main <<< n ==>1234567890<== k: 100000
main <<< superDigit0: 9
main <<<  superDigit: 9


12345678902345678901 100000

main <<< n ==>12345678902345678901<== k: 100000
main <<< superDigit0: 9
main <<<  superDigit: 9


111111111112222222222 100000

main <<< n ==>111111111112222222222<== k: 100000
main <<< superDigit0: 4
main <<<  superDigit: 4


11111111112222222222333333333344444444445555555555 100000

main <<< n ==>11111111112222222222333333333344444444445555555555<== k: 100000
main <<< superDigit0: 6
main <<<  superDigit: 6


111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999 100000

main <<< n ==>111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999<== k: 100000
main <<< superDigit0: 9
main <<<  superDigit: 9


787348562503456834567345634563912387124140124702356758193457345971394519395691340530460134603140611 100000

main <<< n ==>787348562503456834567345634563912387124140124702356758193457345971394519395691340530460134603140611<== k: 100000
main <<< superDigit0: 9
superDigit <<< n ==>41400000<==
superDigit <<< n ==>9<==
main <<<  superDigit: 9


236597883164949013647557503887777957581322677585182091237081212450264153894792080839770354971367849468392849771243717614028258935027765347922552060281345643327741736668 100000

main <<< n ==>236597883164949013647557503887777957581322677585182091237081212450264153894792080839770354971367849468392849771243717614028258935027765347922552060281345643327741736668<== k: 100000
main <<< superDigit0: 8
superDigit <<< n ==>79100000<==
superDigit <<< n ==>17<==
superDigit <<< n ==>8<==
main <<<  superDigit: 8

HackerRank provides three examples. I took it further and generated a few more. Sorry if I went overboard.

For each problem we get two numbers. The first is a string of digits and the second the number of times the string is concatenated to itself. My test scaffolding displays the results of two similarly named functions. Unless I am mistaken, the results match.

After I finished the first function I submitted it to HackerRank. Three tests failed. After some experimenting and reading the constraints, I changed the data type from int to long. The Java code was accepted.

I then figured out that given the first operation one could use streams to compute the sum. I did some research and was able to get to the second solution. We will talk more about it when we take a look at the actual code.

    /**
     * Test scaffolding.
     */
    public static void main(String[] args) {
        
        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // **** read n & k ****
        String[] nk = sc.nextLine().split(" ");

        // **** close scanner ****
        sc.close();

        // **** extract n & k ****
        String n    = nk[0];
        int k       = Integer.parseInt(nk[1]);

        // **** display n & k ****
        System.out.println("main <<< n ==>" + n + "<== k: " + k);
       
        // **** generate and display super digit ****
        System.out.println("main <<< superDigit0: " + superDigit0(n, k));

        // **** generate and display super digit ****
        System.out.println("main <<<  superDigit: " + superDigit(n, k));
    }

I believe the test scaffolding that I generated was quite similar to the one offered by HackerRank. We just read the string and multiplier, generate the answer and display it. Note that in my case I ran two different functions that produce the same result.

    /**
     * Complete the superDigit function below.
     */
    static long superDigit0(String n, long k) {
    
        // **** ****
        long p = 0;

        // **** traverse the string ****
        for (int i = 0; i < n.length(); i++) {

            // **** current digit ****
            long v = n.charAt(i) - '0';

            // **** multiply it by k ****
            v *= k;

            // **** add it to p ****
            p += v;
        }

        // **** call recursive function ****
        long sd = findSD(p);

        // **** return super digit ****
        return (int)sd;
    }

This is the entry point for the solution. It generates the sum of the first string and the multiplier ‘k’. We then call the findSD() function which is a recursive method. Could have blended both into one but as I was thinking it came more natural to split processing. Note the use of long and int. If you switch the long for int, the solution will fail three tests.

    /**
     * Find the super digit of the specified string.
     * Recursive call.
     */
    static long findSD(long p) {

        // **** base condition ****
        if (p <= 9)
            return p;

        // **** sum digits ****
        int sum = 0;
        while (p > 0) {

            // **** ****
            sum += p % 10;

            // **** ****
            p /= 10;
        }

        // **** ****
        p = sum;

        // **** recurse ****
        long sd = findSD(p);

        // **** return the super digit ****
        return sd;
    }

This is the recursive function. It stops when we end up with a single digit which is indicated by having p <= 9. We do some processing which implies generating the sum of digits in ‘p’. We then issue a recursive call to process the new ‘p’. When done, we return the super digit.

These last two functions passed all the tests at HackerRank!

I then did some research to get the processing of the strings with less code. I decided to use streams. Initially I used streams on a two function approach, but after some testing and reading I ended using the following:

    /**
     * Using streams.
     * Recursive call.
     */
    public static int superDigit(String n, int k) {

        // **** initial concatenation of digits ****
        n = n.chars().mapToLong(Character::getNumericValue).sum() * k + "";

        // **** base condition and recursion ****
        return (n.length() > 1) ? superDigit(n, 1) : Character.getNumericValue(n.charAt(0));
    }

The first line produces the sum of all digits. The second determines if we are done or we need to use recursion in the new string of integers. If the length of the string n > 1, we have multiple digits so we need to continue to recursively call the superDigit() function. If we end up with a single digit, we return the value of the first and only digit in the string ‘n’.

You should be able to see the similarities of the two approaches. They perform the same tasks in different ways. Of course the second approach is more elegant and with the proper documentation, easy to follow. BTW, I should have done better with the comments in the last function.

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 2491 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.