LeetCode 2020-11-21: Numbers At Most N Given Digit Set

Numbers At Most N Given Digit Set (hard) の挑戦メモです。

問題の概要

• 1 から 9 までの一桁の数字の配列 digits が与えられるので、この数字だけを使って表現できる数値のうち、n ($1 \le n \le 10^9$) を超えない数値がいくつ存在するかを数え上げる
  • 与えられた数字はすべてを使わなくてもいいし、一種類の数字を 2 回以上利用してもいい

考え方

• まずは簡単なケースを考えてみよう、
  • digits = {1, 3, 5}, n = 1000 とする
  • 一桁の数値は 1, 3, 5 の 3 つ
  • 二桁の数値は 11, 13, 15, 31, 33, 35, 51, 53, 55 の 9 つ、つまりは $3^2$ 個になる
  • 三桁の数値は $3^3 = 27$ 個になる
  • したがって、合計すると 39 個となる
  • このケースなら、単にループを回せば簡単に答えが求められるね ☺️
• 基本的にはこのようなアプローチで数え上げればいいのだけど、n = 351 みたいに n が 10 のべき乗ではないケースはどうしたらいいのだろうか？ 🤔
  • 二桁の数値までは上記と同じようなやり方にでいいとして、問題は三桁の数値の数え上げ
  • digits の数字で構成できる x 桁のすべての数値を列挙して総当りで求めるのはちょっと計算量的に辛そう 😨
  • じゃあ、最上位の桁から順に digits の数字を当てはめてみるのはどうだろう？
• 図で表すとこんな感じ
  • 
  • 最上位の桁をみたときに、5 は n = 351 を確実に超えるので 5xx な数値は数え上げの対象外となる
  • 一方で 1 は n を確実に下回るので、1 から始まる三桁の数値はすべて数え上げの対象になる
    • 具体的な数値の個数は $3^2$ となる
  • 最上位の桁が 3 の場合は上位から二桁目以降の数値次第で数え上げの対象か否かが決まる
    • 二桁目が 3 以下なら数え上げの対象になる
      • 個数は $3 + 3 = 6$ 個になる
    • 5 の場合は一番下位の桁次第になる
      • 1 なら数え上げ対象になるが、3 以上だと対象外になる
• …という処理を再帰で実装すればよいのでは？
• そういうわけで実装 → submit → 一発 accept 🤗
  • Runtime 0ms 達成 💪

コード

class Solution {
    public int atMostNGivenDigitSet(String[] _digits, int n) {
        int[] digits = new int[_digits.length];
        for (int j = 0; j < _digits.length; j++) {
            digits[j] = _digits[j].charAt(0) - '0';
        }
        Arrays.sort(digits);

        int result = 0;
        int s = 1;
        long d;

        for (d = 10; d < n; d *= 10) {
            s *= _digits.length;
            result += s;
        }

        return result + countNumsAtMostN(digits, n, 0, s, d / 10);
    }

    int countNumsAtMostN(int[] digits, int n, long v, int s, long d) {
        if (d == 0) {
            return 1;
        }

        for (int i = digits.length - 1; i >= 0; i--) {
            long nv = v + digits[i] * d;
            if (nv <= n) {
                return s * i + countNumsAtMostN(digits, n, nv, s / digits.length, d / 10);
            }
        }

        return 0;
    }
}