Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Recursive Digit Sum challenge

Sharing is caring!

Problem statement
We define super digit of an integer x using the following rules:

  • If x has only 1 digit, then its super digit is x.
  • Otherwise, the super digit of x is equal to the super digit of the digit-sum of x. Here, digit-sum of a number is defined as the sum of its digits.

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

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

You are given two numbers n and k. You have to calculate the super digit of P.

P is created when number n is concatenated k times. That is, if n = 123 and k = 3, then P=123123123.

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

Constraints
1 \le n \textless 10^{100000}
1 \le k \le 10^{5}

Output Format
Output the super digit of P, where P is created as described above.

Sample Input 0

148 3

Sample Output 0

3

Explanation 0
Here n=148 and k=3, so P=148148148.

super_digit(P) = super_digit(148148148) 
               = super_digit(1+4+8+1+4+8+1+4+8)
               = super_digit(39)
               = super_digit(3+9)
               = super_digit(12)
               = super_digit(1+2)
               = super_digit(3)
               = 3.

Sample Input 1
recursive-digit-sum-input-1

Sample Output 1
recursive-digit-sum-output-1

Solution

public class RecursiveDigitSum {
    private static BigInteger sum(BigInteger p) {
        BigInteger ans = BigInteger.ZERO;

        String num = p.toString();
        for (int i = 0; i < num.length(); i++) {
            ans = ans.add(new BigInteger("" + num.charAt(i)));
        }

        return ans;
    }

    private static BigInteger solve(BigInteger p, int k) {
        BigInteger sum = sum(p);
        BigInteger ksum = sum.multiply(new BigInteger("" + k));
        BigInteger spr = sum(ksum);
        if (spr.toString().length() > 1) {
            return solve(sum(p), k);
        }
        return spr;
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        Scanner in = new Scanner(System.in);

        String n = in.next();
        int k = in.nextInt();

        BigInteger p = new BigInteger(n);
        System.out.println(solve(p, k));
    }
}