Recursive Digit Sum

  • + 5 comments

    I don't like the categorization of this problem as recursion. Some of the test cases are so huge that recursion causes stack overflows / timeouts in many languages (I tried both JS and Python). This modulus solution is great, but it's a little misleading to ask you to write it recursively when this solution is so much more elegant.

    • + 2 comments

      memoize your results that helped me in solving in js with recursion

      • + 1 comment

        Even when i used lru_cache in python , it failed 3 to 4 test cases. Then i tried using a custom memo, it still failed those test cases by exceeding recursion limit. Could you elaborate a bit .

        • + 5 comments

          Java 8 Solution (with Recursion)

          static int superDigit(String n, int k) {
              n = n.chars().mapToLong(Character::getNumericValue).sum() * k
                      + "";
              return (n.length() > 1) ? superDigit(n, 1) :
                                          Character.getNumericValue(n.charAt(0));
          }
          
          • + 1 comment

            I use the same solution above in JS and it sadly times out--I guess the JVM beats node.js in runtime speeds

            • + 1 comment

              @drzaiusx11 This recursive JavaScript solution has passed all test cases in Node.js:

              JavaScript Solution (with Recursion)

              function superDigit(n, k) {
                  n = n.split("").reduce((a, b) => +a + +b) * k + "";
                  return (n.length > 1) ? superDigit(n, 1) : n.charAt(0);
              }
              
              • + 1 comment

                can you please explain why you wrote this +a + +b instead of a+b?. i tried running a+b, but it failed.

                • + 0 comments

                  Late reply, but the reason this works is: ( +a + +b ) coerces each variable with a unary operator ( + ), to assure the addition of two integers and not the concatination of two strings. Then, the integer is being multiplied by the concat multiplier ( * k ) and converted back to a string ( + "" )

          • + 1 comment

            This seems awesome. I just wanted to know why you used n.chars().mapToLong(Character::getNumericValue).sum() * k + ""; I understand you are trying to sum all the characters and multiply by k and converting back to string but this notation i have never used. is this faster than say doing a for loop to find this out? doesnt this take O(x) time where x is the no of chars in string n?

            • + 1 comment

              @Utsav1998 Using Java 8 Stream may NOT be faster than a "for loop" but the Stream is more "fluent" in terms of Functional Programming, and the complexity of that stream is indeed O(x).

              • + 1 comment

                then why the hell we are getting time error when using for loop but not when using streams :(

                • + 0 comments

                  @Singhalr31 For a simple "for" loop (without Collections or Maps), Java 8 Stream "could be" overkill. If you need to iterate over a "LARGE" Collection (or Map) , however, Java 8 may be faster because you could avoid creating LOTS of "intermediate" Objects by simply streaming data in the Collection from one operation to another.

          • + 1 comment

            This is the most elegant solution for Java I have seen

            • + 0 comments

              @rafaelcfreire You're welcome! And this is the true power of Java 8.

          • + 0 comments

            Wow! , this is really awesome. Even i used BigInteger for the problem but TLE occured in test case 8 and 9. Thank you so much @tat_lim for the solution!

      • + 0 comments

        @anirbansaha77 This recursive JavaScript solution has passed all test cases in Node.js:

        JavaScript Solution (with Recursion)

        function superDigit(n, k) {
            n = n.split("").reduce((a, b) => +a + +b) * k + "";
            return (n.length > 1) ? superDigit(n, 1) : n.charAt(0);
        }
        
    • + 0 comments

      Java 8 Solution (with Recursion)

      static int superDigit(String n, int k) {
          n = n.chars().mapToLong(Character::getNumericValue).sum() * k
                  + "";
          return (n.length() > 1) ? superDigit(n, 1) :
                                      Character.getNumericValue(n.charAt(0));
      }
      
    • + 1 comment

      Same in C++. Recursive solution causes Stack Overflow in the huge test cases (7,8,9).

      • + 0 comments

        yeah, same, so what did you do about it?

    • + 0 comments

      @carnegiehall This recursive JavaScript solution has passed all test cases in Node.js:

      JavaScript Solution (with Recursion)

      function superDigit(n, k) {
          n = n.split("").reduce((a, b) => +a + +b) * k + "";
          return (n.length > 1) ? superDigit(n, 1) : n.charAt(0);
      }
      
    • + 5 comments

      python3 solution passed.

      def superDigit(n, k):
          
          def add_digits(string):
              if len(string) == 1:
                  return string
              result = sum(int(s) for s in string)
              return add_digits(str(result))
          
          start = sum(int(s) for s in n) * k
          return add_digits(str(start))
      
      • + 0 comments

        Really nice code. Thank you.

      • + 1 comment

        Does this really work?

        • + 0 comments

          Yes, this solution uses recursion and also does not need the % 9 trick. You can show to yourself that "k" can be multiplied after summing up n by using the problem statement example, n = 9875, and change k from 1 to 5. You'll see that the solutions are multiples of one another, except for when it is 10 (which results in having to sum up the integers)

          Also, you can simplify this answer further, so as not to have a "start" variable:

              def superDigit(n, k):
                      sd = sum(int(s) for s in n)
                      if sd*k < 10:
                              return sd*k
                      else:
                              return superDigit(str(sd*k), 1)
          
      • + 1 comment
        [deleted]