# Digital Roots

### From Progteam

Sorter: | Hjfreyer |
---|---|

Source: | Greater New York 2000 |

Link: | http://acm.pku.edu.cn/JudgeOnline/problem?id=1519 |

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

## Contents |

## 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

- Using Scanner, take the input.

- If the number has only one digit, return the number.

- 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 } } } }

## Additional Remarks

I'm getting right answers for every test case I can think of. The website gives me Runtime Error. Can anybody figure out why?