Monday, August 4, 2014

InterestingDigits

Problem:

TopCoder Problem Statement - InterestingDigits

Overview:

Determine the "interesting" digits for a given base.

Java Source:
01: /*
02: TopCoder
03: Single Round Match: 150
04: Division: 2 / 1
05: Level: 2 / 1
06: Points: 500 / 250
07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1523
08:  */
09: 
10: import java.util.ArrayList;
11: import java.util.List;
12: 
13: public class InterestingDigits {
14: 
15:     /*
16:      * Loops through all 3 or fewer digit multiples of digitBase testing each
17:      * to see if the sum of all digits divides evenly by digitBase
18:      */
19:     private static boolean isInteresting(int digitBase, int base) {
20: 
21:         // The largest 3-digit number in the given base
22:         int max = base * base * base;
23: 
24:         // Loop through all multiples of digit
25:         for (int digitMultiple = digitBase; digitMultiple < max;
26:              digitMultiple += digitBase) {
27: 
28:             if (!(sumOfDigitsDividesEvenly(digitMultiple, digitBase, base))) {
29:                 return false;
30:             }
31:         }
32: 
33:         return true;
34:     }
35: 
36:     /*
37:      * Sums all the digits in multiple and tests to see if it divides evenly
38:      * by digit.  If the result is multi-digit, then sumOfDigitsDividesEvenly()
39:      * is call recursively on the result.
40:      */
41:     private static boolean sumOfDigitsDividesEvenly(int multiple, int digit,
42:                                                     int base) {
43: 
44:         int sum = 0;
45: 
46:         while (multiple > base) {
47: 
48:             int x = 1;
49: 
50:             while ((x * base) < multiple) {
51:                 x *= base;
52:             }
53:             int div = (multiple / x);  // div now contains left-most digit.
54: 
55:             sum += div;
56:             multiple = multiple - (x * div);
57:         }
58: 
59:         sum += multiple;
60: 
61:         /*
62:          * If the result is larger than base, then recursively call
63:          * sumOfDigitsDevidesEvenly() on the result.
64:          */
65:         if (sum > base) {
66:             return sumOfDigitsDividesEvenly(sum, digit, base);
67:         }
68: 
69:         return ((sum % digit) == 0);
70:     }
71: 
72:     /*
73:      * Loops through all digits in the given base.  If the digit is
74:      * interesting for that base, then add it to a List.
75:      * When done, convert the List to an array and return it.
76:      */
77:     public int[] digits(int base) {
78: 
79:         List interestingDigits = new ArrayList<>();
80: 
81:         for (int digit = 2; digit < base; digit++) {
82:             if (isInteresting(digit, base)) {
83:                 interestingDigits.add(digit);
84:             }
85:         }
86: 
87:         // Convert the List to an int[]
88:         int[] retArray = new int[interestingDigits.size()];
89:         int x = 0;
90:         for (int i : interestingDigits) {
91:             retArray[x++] = i;
92:         }
93: 
94:         return retArray;
95:     }
96: }
Notes:

To determine if a digit is interesting, we need to check all of it's 1, 2, and 3 digit multiples. For each multiple, we add up the digits. If this sum is more than one digit, then add up the sum of those digits. When the sum is just 1 digit, it should be divided evenly by our original digit. For example, the digit 9 is interesting in base 10. If we take any multiple, say 9 X 123 = 1107. And 1 + 1 + 0 + 7 = 9 - which is evenly divisible by 9.

The problem gets a little tricky because we must handle various bases. Continuing the example above, 9 is not interesting in base 16. 9 * A = 5A. 5 + A = F which is not evenly divisible by 9. Luckily , there isn't much that needs to change to support working in different bases.

Our main method, digits(), simply iterates through each digit in the current base and tests to see if it is interesting. If so, the digit is added to a List. When done, the List is converted to any int[] and returned. Here, a different base will just alter the number that the loop counts up to. For base 8, we'll stop at 7. For base 16, we'll go up to 15. etc.

isInteresting() iterates through all 1, 2, and 3 digit multiples of the given number, and determines if the sum of those digits is evenly divisible by the original digit. Line 22 calculates the largest possible 3 digit number for the given base. And the increment portion of the for loop goes up by digitBase - that way we only look at multiples.

Finally, sumOfDigitsDividesEvenly() does the real work of determining, well, if the sum of the digits in multiple is evenly divisible by the given digit. The method is recursive, so the check at line 46 breaks the recursion when we get down to a single digit. Inside the while loop, we get the left-most digit, add it to sum, subtract it off of multiple, and repeat. Line 59 adds the final, right-most, digit to sum. Then on line 65, it checks to see if our sum has more than one digit. If so, then sumOfDigitsDividesEvenly() is called recursively using the sum as it's input. If the sum is just one digit (i.e. < base) the we return true if sum is evenly divisible by digit.

There's actually a much simpler way of determining if a number is "interesting". See the solution given in the TopCoder Match Editorials

No comments:

Post a Comment