CodingGyan

Digital Root

easy Math and Number Theory

Problem

Add the digits of n. If the result has more than one digit, add its digits again. Repeat until one digit is left. Print that digit. Solve it in O(1) with a formula.

Constraints

  • 0 <= n <= 9 * 10^15

Examples

Input

9875

Output

2

Solutions

Best approachTime O(1)Space O(1)

Repeating the digit sum gives the same answer as taking the number modulo 9, with 9 instead of 0 for multiples of 9. This replaces a loop by one calculation.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process a number.
 * Input   : One integer n.
 * Output  : The digital root.
 * Approach: A formula with modulo 9.
 * Time    : O(1)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long n) {
        // Step 1: A number and the sum of its digits have the same remainder after division by 9.
        // So the digital root is 0 for 0 and 1 + (n - 1) % 9 for every other number.
        if (n == 0) {
            return 0;
        }
        return 1 + (n - 1) % 9;
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}
Hints (1)
  1. What remainder do a number and its digit sum share?

Try these next