UVa 10922

From Algorithmist
Jump to navigation Jump to search

10922 - 2 the 9s[edit]

Summary[edit]

Given a number which may have many digits, determine whether it is a multiple of 9, and if it is, determine its "9-degree".

Explanation[edit]

Consider some number N, and let S be the sum of digits of N. If S is equal to 9, or if S is divisible by 9, then N is also divisible by 9. This test is fairly simple to make recursive, and the 9-degree is defined to be the depth of the recursion involved. The only problem one should or may have is the meaning of 9-degree. It's the number of times you can sum-up the digits of the sum recursively as long as sum>9.

Gotcha's[edit]

  • The 9-degree of 9 is 1, even though its sum of digits is obviously divisible by 9.

Solutions[edit]

Input[edit]

999999999999999999999
9
9999999999999999999999999999998

Output[edit]

999999999999999999999 is a multiple of 9 and has 9-degree 3.
9 is a multiple of 9 and has 9-degree 1.
9999999999999999999999999999998 is not a multiple of 9.