Challenge: Digital Root

Lab Java Beginner 10 points

The digital root of a number: add up its digits; if the result has more than one digit, add up its digits, and so on until one digit is left. Write it recursively.

Input

One whole number n (0 ≤ n ≤ 2,000,000,000).

Output

The digital root.

Example

Input

Output

Sample input available Sample output available

Editor

Java

Hints

First write digitSum(n) = last digit + digitSum(n / 10).

digitalRoot(n): if n has one digit, return it; otherwise return digitalRoot(digitSum(n)).

Solution explanation

9875 → 29 → 11 → 2. Two small recursive methods, each with a clear base case.

Show solution

import java.util.Scanner;

public class Main {
    static long digitSum(long n) {
        if (n < 10) return n;
        return n % 10 + digitSum(n / 10);
    }

    static long digitalRoot(long n) {
        if (n < 10) return n;
        return digitalRoot(digitSum(n));
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        System.out.println(digitalRoot(n));
    }
}

Output

Answer