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.
  1. Prepare
  2. Algorithms
  3. Recursion
  4. Recursive Digit Sum
  5. Discussions

Recursive Digit Sum

Sort by

recency

|

815 Discussions

|

  • spriyamalar
     + 0 comments
    public static int superDigit(String n, int k) {
    long superdigit = Arrays.stream(n.split("")).mapToLong(Long::valueOf).sum()*k;
    while(superdigit>10) {
        superdigit = Arrays.stream(String.valueOf(superdigit).split("")).mapToLong(Long::valueOf).sum();
    }
    return (int)superdigit;
}

  • saurabh_srivast2
     + 0 comments
    def superDigit(N, K):
    # Write your code here
    return int(N) if K== 1 and len(N) == 1 else superDigit(str(K * sum([int(n) for n in N])), 1)

  • klu_2100080214
     + 0 comments

    The RUNTIME ERROR COMES FOR SOME TEST CASES SINCE THE THE INPUT SIZE OF THE STRING WHEN MULTIPLIED WITH K IT BECOMES HUGE STRING WHICH IS TOUGH PROCESS. SO AT FIRST JUST SUM ALL THE DIGITS IN NUMBER STRING AND MULTIPLY WITH K. FOR EXMP: n='11' k=2 p=n*k p='1111' # this could our naive approach s=4 # sum of all digits. now,

    p= (sum of all digits in n which is equal to 2) * k

    => p=4 #same as our naive approach.

    !/bin/python3

    import math import os import random import re import sys

    def superDigit(n, k): # Write your code here #base condition if len(n)==1: return int(n) s=0 for i in n: s=s+int(i) p=s*k if k>1 else s

    return superDigit(str(p),1)

    if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

n = first_multiple_input[0]

k = int(first_multiple_input[1])

result = superDigit(n, k)

fptr.write(str(result) + '\n')

fptr.close()

  • aeliton
     + 0 comments

    I interpreted the restriction of n < 10^100000 as we would definitely have an input containing at least 10 ^19 characters which would extrapolate 64 bit integers.

    In these circumstances, this solution that passes all the tests would fail:

    int superDigitInt(uint64_t n) {
    if (n < 10)
        return n;
    uint64_t v = 0;
    while (n) {
        v += n % 10;
        n /= 10;
    }
    return superDigitInt(v);
}

int superDigit(string n, int k) {
    auto uncharify = [&k](uint64_t acc, const char c) {
        return acc + int(c - '0');
    };
    // This won't work for n > 10^19
    uint64_t prod = accumulate(n.begin(), n.end(), 0ULL, uncharify) * k;
    return superDigitInt(prod);
}

    A solution that would work for n > 10^19 would require perorm operations with bignum:

    string sumDigits(string n) {
    string result = "0";
    for (int i = n.size() - 1; i >= 0; i--) {
        const char ni  = n[i] - '0';
        const char r = result.back() - '0';
        char sum = ni + r;
        result.back() = '0' + sum % 10;
        char carryOver = sum / 10;
        int pos = result.size() - 2;
        while (pos >= 0 && carryOver > 0) {
            char p = result[pos] - '0';
            sum = carryOver + p;
            result[pos] = '0' + sum % 10;
            carryOver = sum / 10;
        }
        if (carryOver > 0) {
            result.insert(result.begin(), carryOver + '0');
        }
    }
    return result;
}

int superDigit(string n)
{
    if (n.size() == 1) {
        return n.at(0) - '0';
    }
    return superDigit(sumDigits(n));
}

string multiply(string n, int k) 
{
    string result;
    vector<uint8_t> dig;
    for (int i = k; i > 0; i /= 10)
        dig.push_back(i % 10);
    reverse(dig.begin(), dig.end());
    vector<tuple<uint8_t, uint8_t>> t(dig.size() + 1);
    for (int i = 0; i < dig.size(); ++i) {
        n.insert(n.begin(), '0');
    }
    while (n.size() > 0) {
        result.insert(result.begin(), get<0>(t[0]) / 10); 
        const char cur = n.back() - '0';
        for (int i = 0; i < dig.size(); i++) {
            auto &[a, b] = t[i];
            const uint8_t c = get<0>(t[i + 1]);
            const uint8_t prod = cur * dig[i] + b;
            a = c + prod % 10;
            b = prod / 10;
        }
        result.front() = result.front() + get<0>(t[0]) % 10 + '0';
        n.pop_back();
    }
    result.erase(result.begin(), find_if(result.begin(), result.end(),
        [](const char& c) { return c != '0'; }));
    return result;
}

int superDigit(string n, int k)
{
    return superDigit(multiply(n, k));
}

  • yazeroual
     + 0 comments

    c# solution with recursion : 

    if(n.Length == 1){
	return int.Parse(n);
}

//Loop trough the digits and multiply by k, the convert to string again
n = (n.Sum(c => char.GetNumericValue(c))*k).ToString();
return superDigit(n,1);