algorithm - ラッキーチケット（ラッキーナンバーの数を数え、すべての桁の合計が指定されている）

Question

ここに問題があります

1≤N≤50の番号が与えられます。すべてのチケットには2N桁の番号があります。最初のN桁の合計が最後のN桁の合計と等しい場合、チケットをラッキーと呼びます。また、番号のすべての桁の合計が与えられます。あなたの仕事は、すべての桁の指定された合計を持つラッキーナンバーの量を数えることです。

入力22の場合、出力は4（0101、0110、1001、1010）です。

この問題を解決するのを手伝ってもらえますか？最小の複雑さはどれくらいですか？

Answer 1

必要な合計がs、の場合、各半分には合計が必要ですs/2。ここで、次を見つける必要があります。f(n, s/2)数字の合計を持つn桁の数字の数s/2。知っているf(n, s/2)と、1行で答えを得ることができます（自分でそれを理解してみてください）。

計算方法については、これf(n, m)が標準のDPです。のような再帰式がありf(n, m) = f(n-1, m) + f(n-1, m-1) + f(n-1, m-2) + ... + f(n-1, m-9)ます。ここに0, 1, 2, .. 9、指定された番号の最後の桁に対して可能なすべてのオプションがあります。最後の桁がk、の場合、残りは(n-1)桁の合計を含む-longnumberm - kです。

それが役に立てば幸い。

PS問題の制約によると、それを渡すには、ある種の長い演算が必要になります。

Answer 2

private static boolean isLucky(int n) {

    int sum1 = 0;
    int sum2 =0;
    String s = String.valueOf(n);
    System.out.println("After Conversion in String= " + s);
    for (int i = 0; i < (s.length()) / 2; i++) {
        System.out.println("half string === " + s.charAt(i));
        sum1 = sum1 + Character.getNumericValue(s.charAt(i));
    }
    System.out.println("half sum === " + sum1);
    for(int j=(s.length()) / 2 ; j< s.length();j++){
        System.out.println("half string === " + s.charAt(j));
        sum2 = sum2 + Character.getNumericValue(s.charAt(j));
    }
    System.out.println("another half sum === " + sum2);
    if(sum1 == sum2){
        return true;
    }
    return false;
}