# Digital Roots

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by kerry.

 Sorter: Hjfreyer Greater New York 2000 http://acm.pku.edu.cn/JudgeOnline/problem?id=1519

Digital Roots is problem number 1519 on the Peking University ACM site.

## Problem Information

Problem Name: Digital Roots
Problem Number on PKU: 1519
Synopsis: The digital root of a positive integer is found by summing the digits of the integer. If the resulting value is a single digit then that digit is the digital root. If the resulting value contains two or more digits, those digits are summed and the process is repeated. This is continued as long as necessary to obtain a single digit.

## Solver Information

Solver: Eric Hong
Date: February 10, 2008

## Trivia

I tried to go to bed but I wasn't sleepy. I looked for a question that was quick and easy.

## General Strategy

1. Using Scanner, take the input.
2. If the number has only one digit, return the number.
3. Else, recursively return the sum of first digit and N-1 digits .

## Solution

```import java.util.*;

public class Main
{
public static Scanner in;

public static void main(String[] args)
{
in = new Scanner(System.in);
doStuff();
}

public static void doStuff()
{
int N = in.nextInt();

while (N > 0)
{
int num = solve(N);
System.out.println(num);
N = in.nextInt();
}
}

public static int solve(int N)
{
if (N < 10)
{
return N;
}
else
{
String temp = "" + N;
int len = temp.length();
int div = (int) Math.pow(10, len - 1);

return (solve((N / div) +(N % div)));
}
}
}
```

## Solution (Accepted by PKU) #2 in C

So, I used the "casting out nines" approach suggested by Prof. Siegel. It works well, and is very very fast.

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main () {
int a;  //Just a counter
long result; //need a long for strtol()
char new, *old, *xshort;

xshort = (char *)malloc(sizeof(char)*11);  //Check nine characters at a time.
xshort[9]='X';
xshort[10]='\0'; //Just in case, I want strtol() to know that the real number ends at xshort[10] and not read extra '\0' as numeral 0.
while(1) {
a=1;
result=0;
xshort[0]=getcahr();
if (xshort[0]=='0')  //leading zero means end of input.
return;
while(1) {
new=getchar();
if (new=='\n') {           //end of a line, output result
result+=(strtol(xshort,NULL,10)%9);   //casting out nines stuff
result = result%9;
if (result==0)
result=9;
printf("%d\n", result);
break;
}
xshort[a]=new;  //Fill xshort with inout to length of 9.
a++;
if (a==8) {
result+=(strtol(xshort,NULL,10)%9);  //if xshort is full, get modulo 9 and add to result.
a=0;   //reset counter for next pass
}
}
}
}
```