SRM 150 DIV2 Midium(500) - InterestingDigits

初のMedium問題。さすがにこれまでの問題とは違って難しく感じた。4桁未満のチェックでOKという問題文の設定を見落としていて、実装の方針がたたずギブアップ。解説を読んで4桁未満でokということに気づき、何とか実装をこなした。

Problem Statement

The digits 3 and 9 share an interesting property. If you take any multiple of 3 and sum its digits, you get another multiple of 3. For example, 1183 = 354 and 3+5+4 = 12, which is a multiple of 3. Similarly, if you take any multiple of 9 and sum its digits, you get another multiple of 9. For example, 759 = 675 and 6+7+5 = 18, which is a multiple of 9. Call any digit for which this property holds interesting, except for 0 and 1, for which the property holds trivially.

A digit that is interesting in one base is not necessarily interesting in another base. For example, 3 is interesting in base 10 but uninteresting in base 5. Given an int base, your task is to return all the interesting digits for that base in increasing order. To determine whether a particular digit is interesting or not, you need not consider all multiples of the digit. You can be certain that, if the property holds for all multiples of the digit with fewer than four digits, then it also holds for multiples with more digits. For example, in base 10, you would not need to consider any multiples greater than 999.

Definition

  • Class: InterestingDigits
  • Method: digits
  • Parameters: int
  • Returns: int
  • Method signature: int digits(int base) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 64

Notes

  • When base is greater than 10, digits may have a numeric value greater than 9. Because integers are displayed in base 10 by default, do not be alarmed when such digits appear on your screen as more than one decimal digit. For example, one of the interesting digits in base 16 is 15.

Constraints

  • base is between 3 and 30, inclusive.

Solution

import java.util.ArrayList;
import java.util.List;

public class InterestingDigits {

    public int[] digits(int base) {

        List<Integer> list = new ArrayList<Integer>();
        for (int n = 2; n < base; n++) {
            if (isMultipleOf(n, base)) {
                list.add(n);
            }
        }

        int[] ret = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }

    private boolean isMultipleOf(int n, int base) {
        for (int i = 0; i < base; i++) {
            for (int j = 0; j < base; j++) {
                for (int k = 0; k < base; k++) {
                    if (((i * base * base + j * base + k) % n) == 0
                            && (i + j + k) % n != 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

}