We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
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 .
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));
}
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 ( + "" )
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?
@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).
@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.
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!
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));
}
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)
Recursive Digit Sum
You are viewing a single comment's thread. Return to all 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.
memoize your results that helped me in solving in js with recursion
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 .
Java 8 Solution (with Recursion)
I use the same solution above in JS and it sadly times out--I guess the JVM beats node.js in runtime speeds
@drzaiusx11 This recursive JavaScript solution has passed all test cases in Node.js:
JavaScript Solution (with Recursion)
can you please explain why you wrote this +a + +b instead of a+b?. i tried running a+b, but it failed.
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 ( + "" )
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?
@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).
then why the hell we are getting time error when using for loop but not when using streams :(
@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.
This is the most elegant solution for Java I have seen
@rafaelcfreire You're welcome! And this is the true power of Java 8.
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!
@anirbansaha77 This recursive JavaScript solution has passed all test cases in Node.js:
JavaScript Solution (with Recursion)
Java 8 Solution (with Recursion)
Same in C++. Recursive solution causes Stack Overflow in the huge test cases (7,8,9).
yeah, same, so what did you do about it?
@carnegiehall This recursive JavaScript solution has passed all test cases in Node.js:
JavaScript Solution (with Recursion)
python3 solution passed.
Really nice code. Thank you.
Does this really work?
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: