Digital Roots

From Progteam

Revision as of 18:48, 28 February 2008 by Kerry (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by kerry.


Digital Roots
Problem Number 1519
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

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


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?

Personal tools